Cod sursa(job #874383)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct muchie
{
int x;
muchie *leg;
};
bool u[100001];
muchie **v;
void f(int k,muchie *p)
{
u[k]=1;
if(v[k]!=NULL)
{
p=v[k];
if(u[p->x]==0)
f(p->x,p);
while(p->leg!=NULL)
{
p=p->leg;
if(u[p->x]==0)
f(p->x,p);
}
}
}
int main()
{
int n,m,s=0,i,y,z;
fin>>n>>m;
v = new muchie*[n+1];
muchie *p;
for(i=1;i<=n;i++)
v[i]=NULL;
for(i=0;i<m;i++)
{
fin>>y>>z;
if(v[y]==NULL)
{
v[y] = new muchie;
v[y]->x=z;
v[y]->leg=NULL;
}
else
{
p=v[y];
while(p->leg!=NULL)
p=p->leg;
v[0] = new muchie;
p->leg=v[0];
v[0]->x=z;
v[0]->leg=NULL;
}
if(v[z]==NULL)
{
v[z] = new muchie;
v[z]->x=y;
v[z]->leg=NULL;
}
else
{
p=v[z];
while(p->leg!=NULL)
p=p->leg;
v[0] = new muchie;
p->leg=v[0];
v[0]->x=y;
v[0]->leg=NULL;
}
}
for(i=1;i<=n;i++)
{
if(u[i]==0)
{
s++;
f(i,p);
}
}
fout<<s;
}