Cod sursa(job #1514820)

Utilizator HorobaHoroba Daiana Horoba Data 31 octombrie 2015 17:23:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
#include <iostream>


using namespace std;
bool viz[100001];
int n,m;
vector <int> A[100001];
  ifstream fin("dfs.in");
void citire_graf()
{ int x,y;

    fin>>n>>m;// n - nr de noduri m nr de muchii
    // pe urmatoarele m linii se afla extremitatile a m muchii

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;


        A[x].push_back(y);// pun in lista de vecini a lui x pe y
        A[y].push_back(x);//pun in lista de vecini a lui y pe x
    }

}
void df(int nod)
{
    int nr_vecini,i;
    nr_vecini=A[nod].size();
    viz[nod]=true;


    for(i=0;i<nr_vecini;++i)

        if (viz[A[nod][i]]==false)
          df(A[nod][i]);




}
int main()
{int i;
    citire_graf();
    int cnt=0;//cu cnt numar componentele conexe
    for(i=1;i<=n;i++)  viz[i]=false;
    for(i=1;i<=n;i++)
         if (viz[i]==false)
    {
        cnt++;
        df(i);
    }
    ofstream fout("dfs.out");
    fout<<cnt;
    fout.close();

    return 0;
}