Pagini recente » Cod sursa (job #531892) | Cod sursa (job #1743731) | Cod sursa (job #2968949) | Cod sursa (job #169729) | Cod sursa (job #2492297)
#include <stdio.h>
#include <algorithm>
#include <list>
#include <stack>
#include <vector>
const int MAX_N = 100000;
const int MAX_M = 200000;
struct Edge {
int id;
int u;
int v;
int biconnectedId;
int other(int x) const {
return u + v - x;
}
};
std::vector<Edge*> edges[1 + MAX_N];
Edge allEdges[1 + MAX_M];
bool visited[1 + MAX_N];
int parent[1 + MAX_N];
int depth[1 + MAX_N];
int upLink[1 + MAX_N];
int biconnectedComponentCount;
std::vector<int> biconnectedComponent[1 + MAX_M];
std::stack<Edge*> traversedEdges;
void dfs(int u) {
visited[u] = true;
for (Edge* e : edges[u]) {
int v = e->other(u);
if (v != parent[u]) {
if (!visited[v]) {
traversedEdges.push(e);
//printf("<%d> ", e->id);
parent[v] = u;
depth[v] = depth[u] + 1;
upLink[v] = depth[v];
dfs(v);
if (upLink[v] >= depth[u]) {
// a new biconnected component has been detected
biconnectedComponentCount++;
while (e->biconnectedId == 0) {
Edge* edge = traversedEdges.top();
traversedEdges.pop();
biconnectedComponent[biconnectedComponentCount].push_back(edge->u);
biconnectedComponent[biconnectedComponentCount].push_back(edge->v);
edge->biconnectedId = biconnectedComponentCount;
}
std::sort(biconnectedComponent[biconnectedComponentCount].begin(), biconnectedComponent[biconnectedComponentCount].end());
biconnectedComponent[biconnectedComponentCount].resize(
std::unique(biconnectedComponent[biconnectedComponentCount].begin(), biconnectedComponent[biconnectedComponentCount].end())
- biconnectedComponent[biconnectedComponentCount].begin());
}
upLink[u] = std::min(upLink[u], upLink[v]);
} else { // return edges
if (depth[u] > depth[v]) {
traversedEdges.push(e);
//printf(">%d< ", e->id);
upLink[u] = std::min(upLink[u], upLink[v]); // ???
}
}
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
allEdges[i].id = i;
scanf("%d%d", &allEdges[i].u, &allEdges[i].v);
edges[allEdges[i].u].push_back(&allEdges[i]);
edges[allEdges[i].v].push_back(&allEdges[i]);
}
biconnectedComponentCount = 0;
for (int u = 1; u <= n; u++) {
visited[u] = false;
depth[u] = 0;
upLink[u] = 0;
}
parent[1] = 0;
depth[1] = 1;
upLink[1] = 1;
dfs(1);
printf("%d\n", biconnectedComponentCount);
for (int i = 1; i <= biconnectedComponentCount; i++) {
for (int v : biconnectedComponent[i]) {
printf("%d ", v);
}
printf("\n");
}
return 0;
}