Pagini recente » Cod sursa (job #1970930) | Cod sursa (job #1970882) | Cod sursa (job #494323) | Cod sursa (job #1969490) | Cod sursa (job #759694)
Cod sursa(job #759694)
#include <fstream>
#include <cstring>
#define maxN 100001
using namespace std;
ifstream in;
ofstream out;
int T[maxN];
int use[maxN];
inline int root(int nod)
{
if(T[nod]!=nod) T[nod]=root(T[nod]);
return T[nod];
}
int main(int argc,char *argv[])
{
int M,N,x,y;
in.open("dfs.in");
in>>N>>M;
for(int i=1;i<=N;++i) T[i]=i;
for(;M--;)
{
in>>x>>y;
x=root(x);
y=root(y);
if(x!=y) T[y]=x;
}
in.close();
int cnt=0;
memset(use,0,sizeof(use));
for(int i=1;i<=N;++i) root(i);
for(int i=1;i<=N;++i)
if(!use[T[i]])
{
++cnt;
use[T[i]]=1;
}
out.open("dfs.out");
out<<cnt<<'\n';
out.close();
return 0;
}