Cod sursa(job #1814315)

Utilizator gundorfMoldovan George gundorf Data 23 noiembrie 2016 20:46:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#define Nmax 100002
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod
{
    int info;
    nod *urm;
};
///Variabile***___
nod *a[Nmax];
int n,m,viz[Nmax];

void ADD (int x,nod *&p)
{
    nod *q=new nod;
    q->info=x;
    q->urm=p;
    p=q;
}

void Citire ()
{
    int i,x,y;
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        ADD(x,a[y]);
        ADD(y,a[x]);
    }
}
void DFS (int x)
{
    nod *prim;
    prim=a[x];
    for (prim=a[x];prim!=NULL;prim=prim->urm)
        if (viz[prim->info]==0)
        {
            viz[prim->info]=1;
            DFS(prim->info);
        }
}

int main()
{int i,nr_componente_conexe=0;
nod *p;
   Citire();

   viz[1]=1;
   DFS(1);
   nr_componente_conexe++;
   for (i=1;i<=n;i++)
    if (viz[i]==0)
   {
       viz[i]=1;
       DFS(i);
       nr_componente_conexe++;
   }
   fout<<nr_componente_conexe;
    return 0;
}