Pagini recente » Cod sursa (job #1421323) | Cod sursa (job #1400150) | Cod sursa (job #1522362) | Cod sursa (job #2703292) | Cod sursa (job #891751)
Cod sursa(job #891751)
#include <fstream>
using namespace std;
int n,m,start[100001],t[2][200002],viz[100001],c,i;
void citire()
{
int i,k=0,a,b;
ifstream fin("dfs.in");
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>a>>b;
k++;
t[0][k]=b;
t[1][k]=start[a];
start[a]=k;
k++;
t[0][k]=a;
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;
fout.close();
return 0;
}