Dans un réseau d'ordinateurs, certains sont connectés par des câbles de données bidirectionnels. Lorsqu'un ordinateur reçoit des données, il peut les transmettre à tous les ordinateurs directement ou indirectement connectés. L'objectif est de déterminer le nombre minimum d'rodinateurs auxquels il faut entrer les données initialement pour que tous les ordinateurs du réseau les reçoivent éventuellement.

Format d'entrée

La première ligne contient deux entiers n et m, où n représente le nombre d'ordinateurs (sommets) et m le nombre de connexions (arêtes). Les m lignes suivantes décrivent chaque connexion par deux entiers p et q, indiquant une liaison bidirectionnelle entre les ordinateurs p et q.

Format de sortie

Un seul entier représentant le nombre minimum d'ordinateurs à alimenter initialement.

Exemple

Entrée :
4 5
1 2
1 3
2 3
2 1
3 4
Sortie : 1

Une approche naïve pourrait tenter d'utiliser l'algorithme de Dijkstra pour calculer les distances minimales, mais cela s'avère inefficace pour ce problème. Deux méthodes efficaces consistent à utiliser la recherche en profonduer (DFS) ou la structure d'ensemble disjoint (Union-Find) pour identifier les composantes connexes du graphe. Le nombre minimum d'ordinateurs à alimenter correspond au nombre de composantes connexes.

Méthode 1 : Recherche en profondeur (DFS)

On modélise le réseau comme un graphe non orienté. Une recherche en profondeur permet d'explorer toutes les composantes connexes. Chaque fois qu'un nouveau sommet non visité est trouvé, on incrémente le compteur de composantes.

#include <iostream>
#include <vector>
using namespace std;

vector<int> reseau[100005];
bool explore[100005];
int composantes = 0;

void explorer(int sommet) {
    explore[sommet] = true;
    for (int voisin : reseau[sommet]) {
        if (!explore[voisin]) {
            explorer(voisin);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        reseau[u].push_back(v);
        reseau[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!explore[i]) {
            explorer(i);
            composantes++;
        }
    }
    cout << composantes << endl;
    return 0;
}

Méthode 2 : Ensembles disjoints (Union-Find)

Cette structure regroupe les ordinateurs en ensembles basés sur leurs connexions. Après avoir fusionné tous les ensembles liés par des arêtes, le nombre d'ensembles distincts représente le nombre de composantes connexes.

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent;
vector<bool> visite;

int trouver(int x) {
    if (parent[x] != x) {
        parent[x] = trouver(parent[x]);
    }
    return parent[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    visite.resize(n + 1, false);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (a != b) {
            int racineA = trouver(a);
            int racineB = trouver(b);
            parent[racineA] = racineB;
        }
    }
    int resultat = 0;
    for (int i = 1; i <= n; i++) {
        int racine = trouver(i);
        if (!visite[racine]) {
            visite[racine] = true;
            resultat++;
        }
    }
    cout << resultat << endl;
    return 0;
}