Cod sursa(job #3204171)

Utilizator thinkphpAdrian Statescu thinkphp Data 15 februarie 2024 19:56:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define SIZE 100005

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

//folosim STL vector
vector<int> Graph[ SIZE ];
int visited[SIZE],
N, //numarul de noduri
M, //numarul de muchii
componente_conexe; //componentele conexe

void DFS(int node) {

     //marcam nodul ca fiind vizitat
     visited[ node ] = 1;

     for(int i = 0; i < Graph[ node ].size(); ++i) {

         int descendent = Graph[ node ][ i ];

         if(!visited[ descendent ])

            DFS( descendent );
     }
}

int main(int argc, char const *argv[]) {

  fin>>N>>M;
  int x, y;

  //reprezentam graful in liste de adiacenta
  for(int i = 0; i < M; ++i) {

      fin>>x>>y;

      Graph[x].push_back(y);

      Graph[y].push_back(x);
  }

  for(int node = 1; node <= N; node++) {

      if( !visited[ node ] ) {

        componente_conexe++;

        DFS( node );
      }
  }

  //cout<<"Numarul de componente_conexe: "<<componente_conexe;
  fout<<componente_conexe;

  return 0;
}