Pagini recente » Cod sursa (job #2250066) | Cod sursa (job #1009391) | Cod sursa (job #999995) | Cod sursa (job #2842347) | Cod sursa (job #680866)
Cod sursa(job #680866)
#include<cstdio>
#define NMAX 100000
#define MMAX 200000
using namespace std;
int n,m,V[NMAX],T[2][MMAX],start[NMAX],nr;
void citire()
{
freopen("dfs.in","r",stdin);
int i,x,y,u=0;
scanf("%d%d", &n,&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
++u;
T[0][u]=y;
T[1][u]=start[x];
start[x]=u;
++u;
T[0][u]=x;
T[1][u]=start[y];
start[y]=u;
}
}
void bfs(int s)
{
int ic,sf,man, coada[NMAX];
ic=sf=1;
coada[ic]=s;
V[s]=1;
while(ic<=sf)
{
man=start[coada[ic]];
while(man)
{
if(V[T[0][man]]==0)
{
sf++;
coada[sf]=T[0][man];
V[T[0][man]]=1;
}
man=T[1][man];
}
ic++;
}
}
void afisare()
{
freopen("dfs.out","w",stdout);
printf("%d ", nr );
}
int main()
{
citire();
for(int i=1;i<=n;++i)
if(!V[i])
{
bfs(i);
nr++;
}
afisare();
return 0;
}