Cod sursa(job #2276614)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 4 noiembrie 2018 22:21:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100005;

vector<int> g[NMAX];

bool d[NMAX];

void dfs(int root) {
   stack<int> s;
   s.push(root);
   d[root] = true;
   while (!s.empty()) {
      int node = s.top();
      s.pop();
      for (int v : g[node]) {
         if (!d[v]) {
            s.push(v);
            d[v] = true;
         }
      }
   }
}

int main() {
   ifstream iff("dfs.in");
   ofstream off("dfs.out");

   int N, M;
   iff >> N >> M;
   for (int i = 0; i <= N; ++i) {
      d[i] = false;
   }

   for (int i = 0; i < M; ++i) {
      int n1, n2;
      iff >> n1 >> n2;
      g[n1].push_back(n2);
      g[n2].push_back(n1);
   }

   int count = 0;
   for (int i = 1; i <= N; ++i) {
      if (!d[i]) {
         dfs(i);
         count += 1;
      }
   }

   off << count;
   return 0;
}