Cod sursa(job #1376426)

Utilizator Walrus21andrei Walrus21 Data 5 martie 2015 17:22:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <stdio.h>
#include <vector>
#define mN 100001

using namespace std;

int i,N,M,X,Y,c; bool o[mN];
vector <int> G[mN];

void dfs(int n)
{
    o[n]=1;
    for(int i=0;i<G[n].size();i++)
     if(!o[G[n][i]]) dfs(G[n][i]);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
    {
        scanf("%d%d",&X,&Y);
        G[X].push_back(Y);
        G[Y].push_back(X);
    }
    for(i=1;i<=N;i++)
     if(!o[i]) {dfs(i); c++;}
    printf("%d",c);
    return 0;
}