Algorithms-Library/Biconnected Components.cpp at main · Alextz307/Algorithms-Library · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>

using namespace std;

ifstream fin("componentebiconexe.in");
ofstream fout("componentebiconexe.out");

const int kN = 1e5;
vector<int> g[1 + kN];
int timer, tin[1 + kN], low[1 + kN];
vector<pair<int, int>> bridges;
bitset<1 + kN> isAp;
stack<pair<int, int>> st;
vector<vector<int>> bc;

void minSelf(int &x, const int &y) {
  if (y < x) {
    x = y;
  }
}

void dfs(int u, int par) {
  g[u].erase(find(g[u].begin(), g[u].end(), par));
  tin[u] = low[u] = ++timer;
  int children = 0;

  for (int v : g[u]) {
    if (tin[v]) {
      minSelf(low[u], tin[v]);
    } else {
      children += 1;
      st.emplace(u, v);

      dfs(v, u);
      minSelf(low[u], low[v]);

      if (tin[u] <= low[v]) {
        if (tin[u] < low[v]) {
          bridges.emplace_back(u, v);
        }

        if (par) {
          isAp[u] = true;
        }

        bc.push_back({});
        int p, q;
        do {
          tie(p, q) = st.top();
          st.pop();
          bc.back().emplace_back(p);
          bc.back().emplace_back(q);
        } while (p != u || q != v);
      }
    }
  }

  if (!par && children > 1) {
    isAp[u] = true;
  }
}

void TestCase() {
  int task, n, m;
  fin >> task >> n >> m;

  for (int i = 1; i <= m; ++i) {
    int u, v;
    fin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  for (int v = 1; v <= n; ++v) {
    if (!tin[v]) {
      g[v].emplace_back(0);
      dfs(v, 0);
    }
  }

  if (task == 1) {
    fout << bc.size() << '\n';

    for (auto it : bc) {
      sort(it.begin(), it.end());
      it.erase(unique(it.begin(), it.end()), it.end());

      fout << it.size() << ' ';
      for (int v : it) {
        fout << v << ' ';
      }
      fout << '\n';
    }
  } else if (task == 2) {
    fout << isAp.count() << '\n';
    for (int v = 1; v <= n; ++v) {
      if (isAp[v]) {
        fout << v << ' ';
      }
    }
    fout << '\n';
  } else {
    fout << bridges.size() << '\n';
    for (auto it : bridges) {
      fout << it.first << ' ' << it.second << '\n';
    }
  }
}

int main() {
  int tests = 1;

  for (int tc = 1; tc <= tests; ++tc) {
    TestCase();
  }

  fin.close();
  fout.close();

  return 0;
}