Cod sursa(job #3219159)

Utilizator thinkphpAdrian Statescu thinkphp Data 30 martie 2024 11:54:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <vector>
#define SIZE 100009
#define FIN "dfs.in"
#define FOUT "dfs.out"
#define pb push_back

using namespace std;

int N, //numarul de noduri
    M; //numarul de muchii

vector<int> Graph[SIZE];//graph
int visited[SIZE],
compoments;


void read_graph() {

  int x, y;

  freopen(FIN, "r", stdin);

  cin>>N>>M;

  //cout<<N<<M;

  for(int i = 1; i <= M; ++i) {

      cin>>x>>y;

      Graph[x].pb(y);
      Graph[y].pb(x);
  }

}

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 );
            }
     }
}

void find_components_connex() {

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

         if(!visited[ node ]) {

             compoments++;

             DFS(node);
         }
     }

     freopen(FOUT, "w", stdout);
     //cout<<"Numarul de compomente conexe = "<<compoments;
     cout<<compoments;
}

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

   read_graph();
   find_components_connex();

  return 0;
}