Pagini recente » Cod sursa (job #519960) | Borderou de evaluare (job #1711726) | Cod sursa (job #496447) | Cod sursa (job #1295948) | Cod sursa (job #598994)
Cod sursa(job #598994)
#include <stdio.h>
#include <vector>
using namespace std;
long N,M,i,j,x,y,viz[100001],stiva[100001],G[100001],total;
vector <int> A[100001];
void parcurgere_dfs (long start)
{
long p=1,u=1;
int ok;
stiva[1]=start;
while (u)
{
viz[stiva[p]]=1;
ok=0;
for (i=0; i<G[stiva[p]] && !ok; i++) if (!viz[A[stiva[p]][i]]) {stiva[++u]=A[stiva[p]][i]; ok++;}
if (!ok) u--;
p=u;
}
total++;
}
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);
A[x].push_back(y);
A[y].push_back(x);
}
for (i=1; i<=N; i++) G[i]=A[i].size();
for (j=1; j<=N; j++) if (!viz[j]) parcurgere_dfs(j);
printf("%d", total);
return 0;
}