Cod sursa(job #588266)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 7 mai 2011 14:43:43
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream.h>
#define N 100001
typedef struct nod
{long info;
struct nod *leg;}Nod,*list;
typedef struct
{long grin;
list lad;}head;
typedef head graf[N];
graf g;
long n,m,c[N]={0},i,j,k,t=0,s[N],p;

void add(list_ad &l,long x)
{Nod *px=new Nod;
px->info=x;
px->leg=l;
l=px;}

long del(list_ad &l)
{long x=l->info;
Nod *t=l->leg;
free(l);
l=t;
return x;}

int main()
{ifstream f("dfs.in");
ofstream h("dfs.out");
f>>n>>m;
for(i=1;i<=n;i++)
      g[i].grin=0,g[i].lad=NULL;
for(k=1;k<=m;k++)
      {f>>i>>j;
      g[i].grin++;
      g[j].grin++;
      add(g[i].lad,j);
      add(g[j].lad,i);}
for(i=1;i<=n;i++)
if(c[i]==0)
      {t++,p=0;
      s[++p]=i;
      while(p)
              {k=s[p--];
              c[k]=1;
              while(g[k].grin!=0)
                      {j=del(g[k].lad);
                      g[k].grin--;
                      if(c[j]==0)
                                 s[++p]=j;}}}
g<<t;
f.close();
g.close();
return 0;}