Cod sursa(job #2610518)

Utilizator cristi1616Olaru Cristian cristi1616 Data 4 mai 2020 22:54:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
// Copyright 2018 Popescu Alexandru Gabriel <[email protected]>
// Copyright 2018 Darius Neatu <[email protected]>

// Componente biconexe + puncte de articulatie + muchii critice (punti)
// O(n + m)

// https://infoarena.ro/problema/biconex

#include <bits/stdc++.h>

#define NMAX 100010
#define edge pair<int, int>

using namespace std;

class Task {
public:
  void solve() {
    read_input();
    get_result();
    print_output();
  }

private:
  int n, m;
  vector<int> adj[NMAX];
  vector<vector<int>> bcc;
  stack<edge> sc;
  vector<int> found;
  vector<int> low_link;
  vector<int> parent;
  void read_input() {
    ifstream fin("biconex.in");
    fin >> n >> m;
    found = vector<int>(n + 1, -1);
    low_link = vector<int>(n + 1, 0);
    parent = vector<int>(n + 1, 0);
    for (int i = 1; i <= m; ++i) {
      int x, y;
      fin >> x >> y;
      adj[x].push_back(y);
      adj[y].push_back(x);
    }
  }

  void get_result() { tarjan(); }

  void tarjan() {
    int current_start = 0;  
    for (int i = 1; i <= n; ++i) {
      if (found[i] == -1) {
        parent[i] = 0;
        dfs(i, current_start);
      }
    }
  }

  void dfs(int node, int &current_start) {
    ++current_start;
    found[node] = current_start;
    low_link[node] = current_start;
    int children = 0;
    for (auto &vecin : adj[node]) {
      if (found[vecin] == -1) {
        parent[vecin] = node;
        ++children;
        sc.push(edge(node, vecin));
        dfs(vecin, current_start);
        low_link[node] = std::min(low_link[node], low_link[vecin]);
        if (low_link[vecin] >= found[node]) {
          get_bcc(edge(node, vecin));
        }
      } else {
        if (vecin != parent[node]) {
          low_link[node] = std::min(low_link[node], found[vecin]);
        }
      }
    }
  }

  void get_bcc(edge target_edge) {
    vector<int> current_bcc;
    edge current_edge = edge(-1, -1);
    while (current_edge != target_edge) {
      current_edge = sc.top();
      sc.pop();
      current_bcc.push_back(current_edge.first);
      current_bcc.push_back(current_edge.second);
    }
    sort(current_bcc.begin(), current_bcc.end());
    auto it = unique(current_bcc.begin(), current_bcc.end());
    current_bcc.erase(it, current_bcc.end());
    bcc.push_back(current_bcc);
  }

  void print_output() {
    ofstream fout("biconex.out");
    int sol = bcc.size();
    fout << sol << "\n";
    for (int i = 0; i < sol; ++i) {
      for (auto &node : bcc[i]) {
        fout << node << " ";
      }
      fout << '\n';
    }
  }
};

int main() {
  Task *task = new Task();
  task->solve();
  delete task;
  return 0;
}