Cod sursa(job #759689)

Utilizator razeraze raze raze Data 18 iunie 2012 23:08:32
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 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]);
    else T[nod]=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;
        if(root(x)!=root(y)) T[y]=x;
    }

    in.close();

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

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

    out.open("dfs.out");

    out<<cnt<<'\n';

    out.close();

    return 0;
}