Cod sursa(job #1519355)

Utilizator beatrice01Ferco Beatrice beatrice01 Data 7 noiembrie 2015 11:25:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int maxn= 100005;

int n,m,cntConexe;
vector <int> g[maxn]; /// array de vectori
bool vizitat[maxn];
vector <int> comp[maxn];

void dfs (int node)
{
    vizitat[node]= 1;
  //  comp[cntConexe].push_back(node);
//    cout<<node<<" ";
    for (int i=0; i< int(g[node].size()) ; i++)
      {
          int vecin=g[node][i];
          if(!vizitat[vecin])
             dfs(vecin);
      }
}

int main()
{
    ifstream f("dfs.in");
    ofstream gout("dfs.out");
    f>>n>>m;
    for(int i=1;i<=m;i++)
       {
           int x,y;
           f>>x>>y;
           g[x].push_back(y); /// adaug in lista lui x elem y
           g[y].push_back(x); /// adaug in lista lui y elem x
       }

     for(int i=1;i<=n;i++)
      if(!vizitat[i])  /// daca un nod nu e vizitat, parcurgem toate comp conexe ale nodului resp
      {
          ++cntConexe;
          dfs(i);
      }
      gout<<cntConexe<<'\n';
 /*    for(int i=1; i<=cntConexe; i++)
     {
         gout<<"componenta conexa #"<<i<<'\n';
         for(int j=0;j< int(g[i].size()) ; j++)
            gout<<g[i][j]<<" ";
            gout<<'\n';
     }
*/
    return 0;
}