Pagini recente » Cod sursa (job #2599336) | Cod sursa (job #2977526) | Cod sursa (job #1945451) | Cod sursa (job #1053462) | Cod sursa (job #250684)
Cod sursa(job #250684)
#include<stdio.h>
#define N 100005
#define M 200005
/*const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};*/
int *a[N],d[N],x[M],y[M],n,m,viz[N];
void bfs(int x0)
{
int coada[N],u=0,p=0,x,y;
coada[u++]=x0;
viz[x0]=1;
while (u!=p)
{
x=coada[p++];
for (int i=1; i<=a[x][0]; ++i)
{
y=a[x][i];
if (!viz[y])
{
coada[u++]=y;
viz[y]=1;
}
}
}
}
void citire()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=m; ++i)
{
scanf("%d%d",&x[i],&y[i]);
++d[x[i]];
++d[y[i]];
}
for (int i=1; i<=n; ++i)
{
a[i]= new int [1+d[i]];
a[i][0]=0;
}
for (int i=1; i<=m; ++i)
{
a[x[i]][++a[x[i]][0]]=y[i];
a[y[i]][++a[y[i]][0]]=x[i];
}
/*
for (int i=1; i<=n; ++i)
{
printf("vecinii lui %d: ",i);
for (int j=1;j<=a[i][0];++j)
printf("%d ",a[i][j]);
printf("\n");
}
printf("%d",n-s);
*/
}
int calcul()
{
int num=0;
for (int i=1; i<=n; ++i)
{
if (!viz[i])
++num;
bfs(i);
}
return num;
}
int main()
{
citire();
printf("%d\n",calcul());
return 0;
}