Pagini recente » Cod sursa (job #2289264) | Cod sursa (job #2451713) | Cod sursa (job #675769) | Cod sursa (job #2624945) | Cod sursa (job #890259)
Cod sursa(job #890259)
#include <fstream>
using namespace std;
int n,m,start[100001],t[2][200002],viz[100001],c,i;
void citire()
{
int a,b,i,k=0;
ifstream fin("dfs.in");
fin>>n>>m;
for(i=1;i<=n;i++)
{
fin>>a>>b;
k++;
t[0][k]=a;
t[1][k]=start[a];
start[a]=k;
k++;
t[0][k]=b;
t[1][k]=start[b];
start[b]=k;
}
}
void df(int vf)
{
int stiva[100001],i,j,k=0;
k++;
stiva[k]=vf;
viz[vf]=1;
k=1;
while(k>0)
{
i=start[stiva[k]];
while(i!=0 && viz[t[0][i]]==1)
i=t[1][i];
if(i!=0)
{
k++;
stiva[k]=t[0][i];
viz[t[0][i]]=1;
}
else k--;
}
}
int main()
{
ofstream fout("dfs.out");
citire();
for(i=1;i<=n;++i)
if(viz[i]==0)
{
c++;
df(i);
}
fout<<c/2;
fout.close();
return 0;
}