Cod sursa(job #161250)

Utilizator luana_0105Fagarasan Luana luana_0105 Data 17 martie 2008 20:08:00
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#define nmax 100000

typedef struct nod { int inf;
                     nod *urm;
                   };

nod *prim[nmax];
int viz[nmax];
int cnt,n,m;

                   

void read()
{
      int i,n1,n2;
      freopen("dfs.in","r",stdin);
      freopen("dfs.out","w",stdout);
      scanf("%d%d", &n, &m );
      for(i=1;i<=m;i++)
      {
           scanf("%d%d", &n1, &n2);
           nod *p= new nod;
           p->inf=n1;
           p->urm=prim[n2];
           prim[n2]=p;
           nod *q= new nod;
           q->inf=n2;
           q->urm=prim[n1];
           prim[n1]=q;
      }
}

void dfs(int nd)
{
      viz[nd]=cnt;
      for(nod *p=prim[nd]; p!=NULL; p=p->urm)
       if(viz[p->inf]==0)      
              dfs(p->inf);
}


void solve()
{
      int i;
      for(i=1;i<=n;i++)
        if(viz[i]==0)
        {
            ++cnt;
            dfs(i);
        }
}

void print()
{
      printf("%d\n", cnt);
}

int main()
{
    read();
    solve();
    print();
    return 0;
}