Cod sursa(job #1808059)

Utilizator rares00Foica Rares rares00 Data 17 noiembrie 2016 11:30:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
//graf neorientat - sa se gaseasca numarul de componente conexe (DFS, alocare dinamica)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n,m;
int nrCompConexe;
struct nod{
    int vecin;
    struct nod *urm;
}*L[100002],*act;
bool viz[100002];   //vector noduri vizitate

void citeste()
{
    int x,y;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y;
        //adauga nodul x la lista y
        act=new nod;
        act->vecin=x;
        act->urm=L[y];
        L[y]=act;
        //adauga nodul y la lista x
        act=new nod;
        act->vecin=y;
        act->urm=L[x];
        L[x]=act;
    }
}

void dfs(int nod)
{
    struct nod *actual;
    //marcheaza nodul ca vizitat
    viz[nod]=1;
    //ia toate muchiile nodului
    actual=L[nod];
    while(actual!=NULL)
    {
        //parcurge in adancime pentru primul vecin nevizitat
        if(viz[actual->vecin]==0)
            dfs(actual->vecin);
        actual=actual->urm;
    }
}

int main()
{
    citeste();
/*
    for(int i=1;i<=n;++i)
    {
        out<<i<<": ";
        act=L[i];
        while(act!=NULL)
            out<<act->vecin<<" ", act=act->urm;
        out<<"\n";
    }
*/
    //pentru a gasi numarul componentelor conexe
    //ia fiecare nod pe rand, si aplica dfs
    for(int i=1;i<=n;++i)
        if(viz[i]==0)
            ++nrCompConexe, dfs(i);
    //afiseaza numarul de componente conexe
    out<<nrCompConexe<<"\n";

    return 0;
}