Cod sursa(job #759694)

Utilizator razeraze raze raze Data 18 iunie 2012 23:14:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstring>

#define maxN 100001

using namespace std;

ifstream in;
ofstream out;

int T[maxN];
int use[maxN];

inline int root(int nod)
{
    if(T[nod]!=nod) T[nod]=root(T[nod]);
    return T[nod];
}

int main(int argc,char *argv[])
{
    int M,N,x,y;

    in.open("dfs.in");

    in>>N>>M;
    
    for(int i=1;i<=N;++i) T[i]=i;

    for(;M--;)
    {
        in>>x>>y;

        x=root(x);
        y=root(y);

        if(x!=y) T[y]=x;
    }

    in.close();

    int cnt=0;
    memset(use,0,sizeof(use));

    for(int i=1;i<=N;++i) root(i);

    for(int i=1;i<=N;++i)
        if(!use[T[i]])
        {
            ++cnt;
            use[T[i]]=1;
        }

    out.open("dfs.out");

    out<<cnt<<'\n';

    out.close();

    return 0;
}