Cod sursa(job #2122139)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 4 februarie 2018 18:01:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAXN = 100000;

vector <int>g[MAXN + 1];
bool viz[MAXN + 1];

int n, m;

void dfs(){
  int cnt = 0;
  for (int i = 1; i <= n; ++ i){
    if (!viz[i]){
      cnt ++;
      stack <int>stiva;
      stiva.push(i);
      viz[stiva.top()] = true;
      while (stiva.size()){
        int cr = stiva.top();
        stiva.pop();
        for (auto x = g[cr].rbegin(); x != g[cr].rend(); ++ x){
          if (!viz[*x]){
            viz[*x] = true;
            stiva.push(*x);
          }
        }
      }
    }
  }

  out << cnt;

}


int main(){
  in >> n >> m;

  for (int i = 1; i <= m; ++ i){
    int a, b;
    in >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  dfs();

  return 0;
}