Pagini recente » Rating berian grartian (beriangratian) | Cod sursa (job #2218553) | Statisticile problemei Loterie | Cod sursa (job #1503233) | Cod sursa (job #1970921)
#include <vector>
#include <stack>
#include <fstream>
#include <iostream>
using namespace std;
class BCC {
int n;
vector<vector<int>> G, bcs;
vector<bool> isAncestor;
vector<int> depth, lowlink, wh;
stack<int> st;
void dfs(int x, int f) {
depth[x] = depth[f] + 1;
lowlink[x] = depth[x];
st.push(x);
isAncestor[x] = true;
for (auto y : G[x]) {
if (y == f)
continue;
if (!depth[y]) {
// DFS edge.
dfs(y, x);
lowlink[x] = min(lowlink[x], lowlink[y]);
// x is critical node.
if (lowlink[y] >= depth[x]) {
vector<int> bc;
while (st.top() != x) {
wh[st.top()] = bcs.size();
bc.push_back(st.top());
st.pop();
}
bc.push_back(x);
bcs.push_back(bc);
}
// Critical Edge.
if (lowlink[y] > depth[x]) {
}
} else if (isAncestor[y]) {
// Back edge.
lowlink[x] = min(lowlink[x], depth[y]);
} else {
// Forward edge.
}
}
isAncestor[x] = false;
}
public:
BCC(vector<vector<int>>& G) : G(G) {
n = G.size() - 1;
depth = lowlink = wh = vector<int>(n+1);
isAncestor = vector<bool>(n+1);
for (int i = 1; i <= n; ++i) {
if (!depth[i]) {
dfs(i, 0);
}
}
}
vector<vector<int>> getBcs() {
return bcs;
}
};
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m;
cin >> n >> m;
vector<vector<int>> G(n+1);
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
// cerr << "Here" << endl;
BCC bcc(G);
auto bcs = bcc.getBcs();
cout << bcs.size() << "\n";
for (auto& bc : bcs) {
for (auto el : bc) {
cout << el << " ";
}
cout << "\n";
}
}