Pagini recente » Cod sursa (job #2930359) | Cod sursa (job #2520316) | Cod sursa (job #1216496) | Cod sursa (job #2814310) | Cod sursa (job #1947810)
/**
* Worg
*/
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using std::pair;
using std::stack;
using std::vector;
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);
const int kMaxN = 1 + 100000;
/*-------- Input data --------*/
int N, M;
vector<int > graph[kMaxN];
/*-------- Biconnected components data --------*/
int level[kMaxN], dp[kMaxN];
stack<pair<int, int > > edge_stack;
vector<int > comp;
vector<vector<int > > bc_comps;
/*-------- --------*/
void ReadInput() {
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++) {
int u, v; scanf("%d%d", &u, &v);
graph[u].push_back(v); graph[v].push_back(u);
}
}
void AddComponent(const pair<int, int > stop) {
pair<int, int > edge;
do {
edge = edge_stack.top(); edge_stack.pop();
comp.push_back(edge.first); comp.push_back(edge.second);
}while(edge != stop);
std::sort(comp.begin(), comp.end());
comp.erase(std::unique(comp.begin(), comp.end()), comp.end());
bc_comps.push_back(comp); comp.clear();
}
void DFS(int node = 1, int father = 0) {
dp[node] = level[node];
for(int nxt : graph[node]) {
if(!level[nxt]) {
edge_stack.push(std::make_pair(node, nxt));
level[nxt] = level[node] + 1;
DFS(nxt, node);
if(dp[nxt] >= level[node]) {
AddComponent(std::make_pair(node, nxt));
}
}
}
bool ok_father = false;
for(int nxt : graph[node]) {
if(nxt == father && !ok_father) {
ok_father = true;
} else {
dp[node] = std::min(dp[node], dp[nxt]);
}
}
}
void WriteOutput() {
printf("%d\n", (int)bc_comps.size());
for(auto bc_comp : bc_comps) {
for(auto node : bc_comp) {
printf("%d ", node);
}
printf("\n");
}
}
int main() {
ReadInput();
level[1] = 1; DFS();
WriteOutput();
return 0;
}