Cod sursa(job #694436)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 27 februarie 2012 21:02:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
#include<vector>
#include<bitset>

using namespace std;

#define Nmax 100001

vector<int> G[Nmax];
bitset<Nmax> use;
//int T[Nmax], D[Nmax], F[Nmax], timp;
int N, M, nrcomp;

void DF(int nod) {
    use[nod]=1;
    //D[nod]=++timp;
    //printf("%d ",nod);
    for(vector<int>:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
        if(!use[*it]) {
            //T[*it]=nod;
            DF(*it);
        }
    //F[nod]=++timp;
}

int main() {
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    int i, j;

    scanf("%d %d",&N,&M);
    while(M--) {
        scanf("%d %d",&i,&j);
        G[i].push_back(j);
        G[j].push_back(i);
    }
    for(i=1; i<=N; i++)
        if(!use[i]) {
            DF(i);
            ++nrcomp;
            //printf("\n");
        }

    /*for(i=1; i<=N; i++)
        printf("%d ",T[i]);
    printf("\n");*/
    printf("%d\n",nrcomp);

    return 0;
}