Cod sursa(job #412017)

Utilizator PopaStefanPopa Stefan PopaStefan Data 5 martie 2010 12:07:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#define nmax 100001

using namespace std;

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

int n,m,viz[nmax];

struct nod
   {int inf;
    struct nod *urm;
   };
nod *l[nmax];

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

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

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