Cod sursa(job #282412)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 17 martie 2009 17:00:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
using namespace std;

struct nod { int inf; nod *adr;};
nod *v[100010];

int i,n,m,x,y,viz[100010],sol;

void creare(int i,int j)

 { nod *c;

   c=new nod;
   c->inf=j;
   c->adr=v[i];
   v[i]=c;

   c=new nod;
   c->inf=i;
   c->adr=v[j];
   v[j]=c;
 }
void dfs(int i)

 {  nod *p;
    viz[i]=1;

    for(p=v[i];p;p=p->adr)

     if(!viz[p->inf]) dfs(p->inf);
 }
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f>>n>>m;
for(i=1;i<=m;i++)
 {f>>x>>y; creare(x,y);}
for(i=1;i<=n;i++)
 if(!viz[i]) { sol++; dfs(i);}
g<<sol;
f.close();
g.close();
return 0;
}