Pagini recente » Cod sursa (job #2148285) | Cod sursa (job #2200419) | Cod sursa (job #885345) | Cod sursa (job #1453412) | Cod sursa (job #398438)
Cod sursa(job #398438)
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int *a[100001];
int n,m,viz[100001],nr;
void citire()
{
freopen("dfs.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
a[i]=(int *) realloc(a[i],sizeof(int));
a[i][0]=0;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d %d",&x,&y);
a[x][0]++;
a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
a[y][0]++;
a[y]=(int *)realloc(a[y], (a[y][0]+1)*sizeof(int));
a[y][a[y][0]]=x;
}
/*for(int i=1;i<=n;i++)
for(int j=1;j<=a[i][0];j++)
cout<<i<<" "<<a[i][j]<<endl;*/
}
void dfs(int x)
{
viz[x]=1;
for(int i=1;i<=a[x][0];i++)
if(viz[a[x][i]]==0)
dfs(a[x][i]);
}
int main()
{
citire();
for(int k=1;k<=n;k++)
if(viz[k]==0)
{
nr++;
dfs(k);
}
freopen("dfs.out","w",stdout);
printf("%d",nr);
return 0;
}