Cod sursa(job #1376426)
Utilizator | 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;
}