Cod sursa(job #1617375)

Utilizator Master011Dragos Martac Master011 Data 27 februarie 2016 13:12:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<cstdio>
using namespace std;

const int nMax = 100000 + 1;
int t[nMax];
bool dif[nMax];

int rad(int a){
    if(t[a] == a) return a;
    int r = rad(t[a]);
    t[a] = r;
    return r;
}

int main (){
    FILE *in = fopen("dfs.in","r");
    FILE *out = fopen("dfs.out","w");

    int n, m, x, y;
    fscanf(in,"%d%d", &n, &m);

    for(int i = 1 ; i <= n ; ++i) t[i] = i;

    for(int i = 1 ; i <= m ; ++i){
        fscanf(in,"%d%d", &x, &y);
        t[rad(x)] = rad(y);
    }

    int sol = 0, u;
    for(int i = 1 ; i <= n ; ++i){
        u = rad(i);
        if(dif[u] == false){
            dif[u] = true;
            sol++;
        }
    }

    fprintf(out,"%d\n", sol);
    return 0;
}