Pagini recente » Cod sursa (job #2972472) | Cod sursa (job #2343360) | Cod sursa (job #1652105) | Cod sursa (job #126159) | Cod sursa (job #891850)
Cod sursa(job #891850)
#include <fstream>
using namespace std;
int tata[100001];
void updatetata(int a, int b)
{
if(tata[b]!=-1)updatetata(a,tata[b]);
if(b!=a)tata[b]=a;
}
int main()
{
ifstream fcin("dfs.in");
ofstream fcout("dfs.out");
int m,i,a,b,n,k=0;
fcin>>n>>m;
for(i=1;i<=m;i++)
{fcin>>a>>b;
if(tata[a]==0&&tata[b]==0){tata[a]=-1;tata[b]=a;}
else if(tata[a]==0&&tata[b]==-1){tata[a]=b;}
else if(tata[b]==0&&tata[a]==-1){tata[b]=a;}
else if(tata[a]==-1&&tata[b]==-1){tata[b]=a;}
else {while(tata[a]!=-1)a=tata[a];
updatetata(a,b);}
}
for(i=1;i<=n;i++)
if(tata[i]==-1||tata[i]==0)k++;
fcout<<k<<'\n';
return 0;
}