Cod sursa(job #363494)

Utilizator PopaStefanPopa Stefan PopaStefan Data 13 noiembrie 2009 16:32:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#define Nmax 1000001

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n,viz[Nmax],nr;

struct nod
  {int info;
   nod *urm;
  };
nod *l[Nmax];

void citire()
{int m,x,y,i;
fin>>n>>m;
for(i=1;i<=m;i++)
  {fin>>x>>y;
  nod *c;
  c=new nod;
  c->info=y;
  c->urm=l[x];
  l[x]=c;
  c=new nod;
  c->info=x;
  c->urm=l[y];
  l[y]=c;
  }
}

void dfs(int x)
{nod *c;
viz[x]=1;
for(c=l[x];c!=NULL;c=c->urm)
   if(viz[c->info]==0)
     dfs(c->info);
}

int main()
{citire();
for(int i=1;i<=n;i++)
  if(viz[i]==0)
    {nr++;
     dfs(i);
    }
fout<<nr;
fin.close();
fout.close();
return 0;
}