Cod sursa(job #2798002)

Utilizator CalinCruceanu3576Cruceanu CalinCruceanu3576 Data 10 noiembrie 2021 20:13:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin( "dfs.in" );
ofstream fout( "dfs.out" );
 
class Graf{
private:

    int N;                   
    vector< vector<int> > adc;
    vector<int> viz;

    void Dfs(int nod);
      
public:

    Graf(int n);
    void AdaugaMuchie(int x, int y, int c);
    int CompConexe();
};

void Graf :: Dfs(int nod) {
  int i, w;
  viz[nod] = 1;
  for(i = 0; i < adc[nod].size(); i++) {
      w = adc[nod][i];
      if(viz[w] == 0)
          Dfs(w);
      }
}

Graf :: Graf(int n) {
  N = n;
  adc.resize( n + 1 );
  viz.resize( n + 1 );
}

void Graf :: AdaugaMuchie(int x, int y, int c = 0) {
  adc[x].push_back(y);
  adc[y].push_back(x);
}

int Graf :: CompConexe() {
  int i, conexe;
  conexe = 0;
  for(i = 1; i <= N; i++)
      viz[i] = 0;
  for(i = 1; i <= N; i++)
      if( viz[i] == 0 ) {
          Dfs( i );
          ++conexe;
          }
  return conexe;
}
 
int main()
{
    int n, m , x, y, i;
    fin>>n>>m;
    Graf G(n);
    for(i = 1; i <= m; i++) {
        fin >> x >> y;
        G.AdaugaMuchie( x, y);
    }
    fout << G.CompConexe();
    return 0;
}