Cod sursa(job #662241)
#include<iostream>
#include<fstream>
#include<cstring>
#define nmax 100005
#define mmax 500005
using namespace std;
ifstream f("DFS.in",fstream::in);
ofstream g("DFS.out",fstream::out);
typedef struct
{unsigned int inc,sf;}muchie;
muchie m[mmax];
unsigned int l[nmax];
unsigned int n,mm,distinct[nmax];
void read()
{f>>n>>mm;
for(unsigned int i=1;i<=mm;i++)
f>>m[i].inc>>m[i].sf;
}
void init()
{for(unsigned int i=1;i<=n;i++)
l[i]=i;
}
void kruskal()
{unsigned int xx,j,yy,k=1,i=1;
while(k<n && i<=mm)
{if(l[m[i].inc]!=l[m[i].sf])
{k++;
xx=l[m[i].sf];
yy=l[m[i].inc];
for(j=1;j<=n;j++)
if(l[j]==xx)
l[j]=yy;
}
i++;
}
}
void show_l()
{unsigned int i;
for(i=1;i<=n;i++)
cout<<l[i]<<" ";
cout<<"\n";
}
unsigned int solve()
{unsigned int nrdistinct=0;
unsigned int i,j;
bool q;
for(i=1;i<=n;i++)
{ q=1;
for(j=1;j<=nrdistinct;j++)
if(distinct[j]==l[i])
q=0;
if(q)
distinct[++nrdistinct]=l[i];
}
return nrdistinct;
}
int main()
{read();
init();
//show_l();
kruskal();
// show_l();
g<<solve();
f.close();
g.close();
return 0;
}