Cod sursa(job #167673)
//componente conexe
#include<fstream.h>
#define dim 100001
long n,m,max;
int w[dim];
struct nod
{long info;
nod *urm;
} *v[dim],*p,*ult[dim];
void adauga(long x,long y)
{//lista lui x,daca nu exista o creem
if(v[x]==0)
{v[x]=new nod;
v[x]->info=y;
v[x]->urm=0;
ult[x]=v[x];
}
else //altfel ii adaugam pe y
{p=new nod;
p->info=y;
p->urm=0;
ult[x]->urm=p;
ult[x]=ult[x]->urm;
}
//lista lui y,la fel ca la x
if(v[y]==0)
{v[y]=new nod;
v[y]->info=x;
v[y]->urm=0;
ult[y]=v[y];
}
else
{p=new nod;
p->info=x;
p->urm=0;
ult[y]->urm=p;
ult[y]=ult[y]->urm;
}
}
void dfs(long i)
{w[i]=1;
if(v[i])
{if(!w[v[i]->info])
dfs(v[i]->info);
while(v[i]->urm)
{v[i]=v[i]->urm;
if(!w[v[i]->info])
dfs(v[i]->info);
}
}
}
int main()
{ifstream f("dfs.in");
f>>n>>m;
long i,x,y;
for(i=1;i<=m;i++)
{f>>x>>y;
adauga(x,y);
}
for(i=1;i<=n;i++)
if(!w[i]){max++;dfs(i);}
ofstream g("dfs.out");
g<<max<<'\n';
g.close();
return 0;
}