Pagini recente » Cod sursa (job #1969490) | Cod sursa (job #759694) | Cod sursa (job #2388725) | Cod sursa (job #2930225) | Cod sursa (job #759689)
Cod sursa(job #759689)
#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]);
else T[nod]=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;
if(root(x)!=root(y)) T[y]=x;
}
in.close();
int cnt=0;
memset(use,0,sizeof(use));
for(int i=1;i<=N;++i)
{
root(i);
if(!use[T[i]])
{
++cnt;
use[T[i]]=1;
}
}
out.open("dfs.out");
out<<cnt<<'\n';
out.close();
return 0;
}