Cod sursa(job #1144583)

Utilizator ciubakkaCiobotarasu Vlad ciubakka Data 17 martie 2014 12:31:48
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#define nr 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,c,viz[nr];

typedef struct nod
{
    int nd;
    nod *next;
} *pnod;
pnod v[nr];

void add(pnod &a, int b)
{
    pnod p;
    p=new nod;
    p->nd=b;
    p->next=a;
    a=p;
}

void read()
{
   f>>n>>m;
   int i,x,y;
   for(i=1;i<=m;++i)
   {
       f>>x>>y;
       add(v[x],y);
       add(v[y],x);
   }
}

void DFS(int a)
{
    pnod p;
    viz[a]=1;
    for(p=v[a];p!=NULL;p=p->next)
        if(!viz[p->nd])
        DFS(p->nd);
}
int main()
{
    int i;
    for(i=1;i<=m;++i)
     if(!viz[i])
    {
      c++;
      DFS(i);
    }
    cout<<c;
    return 0;
}