Pagini recente » Cod sursa (job #1540849) | Cod sursa (job #2135069) | Cod sursa (job #1198432) | Cod sursa (job #254911) | Cod sursa (job #162112)
Cod sursa(job #162112)
#include<stdio.h>
#define N 101000
#define M 201000
int n,m,*a[N],d[N];
bool viz[N];
struct muchie{
int x,y;
};
muchie v[M];
void citire()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
++d[v[i].x];
++d[v[i].y];
}
for(int i=1;i<=n;++i){
a[i]=new int[d[i]+1];
a[i][0]=0;
}
for(int i=1;i<=m;++i){
a[v[i].x][++a[v[i].x][0]]=v[i].y;
a[v[i].y][++a[v[i].y][0]]=v[i].x;
}
}
void dfs(int x)
{
viz[x]=true;
for(int i=1;i<=a[x][0];i++)
if(!viz[a[x][i]])
dfs(a[x][i]);
}
int componente(){
int nr=0;
for(int i=1;i<=n;++i)
if(!viz[i]){
dfs(i);
++nr;
}
return nr;
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
printf("%d\n",componente());
return 0;
}