Pagini recente » Cod sursa (job #619834) | Cod sursa (job #401485) | Cod sursa (job #1270291) | Cod sursa (job #151316) | Cod sursa (job #147454)
Cod sursa(job #147454)
#include<fstream.h>
long n,viz[100001],nrc;
long m,st[100001];
struct nod{int x; nod*urm;} *l[100001];
void dfs(int v)
{nrc++;
int vf=1; viz[v]=nrc;
while (vf)
{ nod*p=l[st[vf]];
while (p&&viz[p->x]) p=p->urm;
if(p){vf++; st[vf]=p->x;
viz[p->x]=nrc;}
else vf--;}
}
int main()
{int i,v1,v2;
ifstream f("dfs.in");
f>>n>>m;
for(i=1;i<m+1;i++)
{f>>v1>>v2;
nod *p=new nod;p->x=v1;p->urm=l[v2];
l[v2]=p;
nod *q=new nod;q->x=v2;q->urm=l[v1];
l[v1]=q;
}f.close();
for(i=1;i<n+1;i++)
if(viz[i]==0) dfs(i);
ofstream g("dfs.out");
g<<nrc<<"\n";
g.close();
return 0;}