Pagini recente » Cod sursa (job #2925364) | Cod sursa (job #468722) | Cod sursa (job #2589309) | Cod sursa (job #1964300) | Cod sursa (job #184722)
Cod sursa(job #184722)
#include<stdio.h>
struct nod
{
int x,y;
};
nod mu[200010];
int *v[100010],m,n;
bool viz[100010];
int cat[100010];
void citeste()
{
int i,aux1,aux2;
for(i=1; i<=m; i++)
{
scanf("%d%d",&mu[i].x,&mu[i].y);
cat[mu[i].x]++;
cat[mu[i].y]++;
}
for(i=1; i<=n; i++)
{
v[i]=new int[cat[i]+2];
v[i][0]=0;
}
for(i=1; i<=m; i++)
{
aux1=mu[i].x;
aux2=mu[i].y;
v[aux1][++v[aux1][0]]=aux2;
v[aux2][++v[aux2][0]]=aux1;
}
}
void dfs(int k)
{
int i;
viz[k]=true;
for(i=1; i<=v[k][0]; i++)
{
if(!viz[v[k][i]])
dfs(v[k][i]);
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
citeste();
int i,r=0;
for(i=1; i<=n; i++)
{
if(!viz[i])
{
dfs(i);
r++;
}
}
printf("%d\n",r);
return 0;
}