Pagini recente » Cod sursa (job #1251994) | Cod sursa (job #741239) | Cod sursa (job #149003) | Cod sursa (job #159179) | Cod sursa (job #316502)
Cod sursa(job #316502)
#include<cstdio>
#include<vector>
#define MAXN 100005
using namespace std;
int i , j , k , path[MAXN] ,comp , N , M , a, b , stack[MAXN] , top;
vector <int> G[MAXN];
void read()
{
scanf("%d %d",&N,&M);
for( ; M --; ) {
scanf("%d %d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
}
void DFS ( int X )
{
int j , top = 0 , ok ;
stack[++top] = X;
while(top)
{
X = stack[top] , ok = 0 , path[X] = 1;
for( j = 0 ; j < G[X].size() ; ++j)
if(!path[G[X][j]] ) {ok = 1 ; break;}
if(ok) stack[++top] = G[X][j] ;
else --top;
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
read();
for( i = 1 ; i <= N ; i++)
if(!path[i]) comp++ , DFS(i);
printf("%d\n",comp);
return 0;
}