Cod sursa(job #386843)

Utilizator PopaStefanPopa Stefan PopaStefan Data 26 ianuarie 2010 10:40:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#define nmax 100001

using namespace std;

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

int n,componente[nmax];

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

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

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

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