Cod sursa(job #2924828)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 11 octombrie 2022 17:34:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5;

int n;
int m;
int cc;
vector< vector<int> > graph;
vector<bool> seen;
vector<bool> inStack;

vector< pair<int, int> > backEdges;
vector< pair<int, int> > traverseEdges;
vector< pair<int, int> > advanceEdges;

void read() {
  cin >> n >> m;
  graph.resize(n + 1);
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
}

void dfs(int node) {
  seen[node] = true;
  inStack[node] = true;

  for (int ngh: graph[node]) {
    if (!seen[ngh]) {
      advanceEdges.push_back(make_pair(node, ngh));
      dfs(ngh);
    }
    else if (inStack[ngh]) {
      backEdges.push_back(make_pair(node, ngh));
    }
    else {
      traverseEdges.push_back(make_pair(node, ngh));
    }
  }
}

void print() {
  cout << cc;
}

int main() {
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);

  read();
  
  seen.resize(n + 1);
  inStack.resize(n + 1);
  cc = 0;
  for (int i = 1; i <= n; i++)
    if (!seen[i]) {
      cc++;
      dfs(i);
    }

  print();

  return 0;
}