Cod sursa(job #930672)

Utilizator AndreiTeodorAndrei R AndreiTeodor Data 27 martie 2013 19:34:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<iostream>
using namespace std;
struct nod
 {int nd;
  nod *next;};
nod *L[100005];
int viz[100005],N,vf,S[100005],M;
void df()
{ nod *c;
int nr;
if(vf)
    { c=L[S[vf]];
     // cout<<S[vf]<<" ";
      vf--;
       while(c)
          { nr=c->nd;
            if(viz[nr]==0)
                {vf++;
                 S[vf]=nr;
                 viz[nr]=1;}
            c=c->next;
          }
        df();
    }
}
int main()
 
{ifstream f("dfs.in");
ofstream g("dfs.out");
int i,j,nr=0;
nod  *p,*q;
f>>N>>M;
while(f>>i>>j)
  {p=new nod;
   p->nd=j;
   p->next=L[i];
   L[i]=p;
   q=new nod;
   q->nd=i;
   q->next=L[j];
   L[j]=q;
   }
f.close();
 
for(int k=1;k<=N;k++)
 if(viz[k]==0)
   { viz[k]=1;
    vf=1;
    S[vf]=k;
    df();
    nr++;}
   g<<nr;
return 0;
}