Pagini recente » Cod sursa (job #3366238) | Cod sursa (job #3366237) | Cod sursa (job #3365573) | Cod sursa (job #3364728) | Cod sursa (job #3364729)
#include <bits/stdc++.h>
const int MAX_N = 500001;
const int MAX_M = 500001;
int t_global = 0;
int t_in[MAX_N], vmin[MAX_N];
std::vector<int> st;
std::vector<int> graph[MAX_N];
struct Edge {
int a, b;
int other(int x) {
return a ^ b ^ x;
}
};
Edge edges[MAX_M];
std::vector<std::vector<int>> bccs;
void dfs(int node, int parent_edge) {
++t_global;
vmin[node] = t_in[node] = t_global;
for (auto it : graph[node]) {
int son = edges[it].other(node);
if (t_in[son] == 0) {
st.push_back(it);
dfs(son, it);
vmin[node] = std::min(vmin[node], vmin[son]);
if (vmin[son] >= t_in[node]) {
std::vector<int> bcc;
int x;
do {
x = st.back();
bcc.push_back(edges[x].a);
bcc.push_back(edges[x].b);
st.pop_back();
} while (x != it);
std::sort(bcc.begin(), bcc.end());
bcc.resize(std::unique(bcc.begin(), bcc.end()) - bcc.begin());
bccs.push_back(bcc);
}
} else if (it != parent_edge)
vmin[node] = std::min(vmin[node], t_in[son]);
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int N; std::cin >> N;
int M; std::cin >> M;
for (int i = 0; i < M; i++) {
int a; std::cin >> a;
int b; std::cin >> b;
edges[i] = {a, b};
graph[a].push_back(i);
graph[b].push_back(i);
}
for (int i = 1; i <= N; i++)
if (t_in[i] == 0) {
dfs(i, -1);
if (graph[i].size() == 0)
bccs.push_back({i});
}
std::cout << bccs.size() << "\n";
for (auto bcc : bccs) {
// std::cout << bcc.size() << " ";
for (auto it : bcc)
std::cout << it << " ";
std::cout << "\n";
}
return 0;
}