Pagini recente » Cod sursa (job #520821) | Cod sursa (job #3203926) | Cod sursa (job #2684228) | Cod sursa (job #1744752) | Cod sursa (job #2213135)
#include <climits>
#include <cstdio>
#include <cstring>
#include <set>
#include <stack>
#define NMAX 100000
#define MMAX 200000
static struct edge {
int n, v, bcc;
} edges[2*MMAX+1];
static struct pair {
int u, v;
} bridges[2*MMAX+1];
static enum c {
WHITE,
GRAY,
BLACK
} color[NMAX];
inline static int min(int a, int b)
{
return a < b ? a : b;
}
static int adj[NMAX], low[NMAX], is_art[NMAX], d[NMAX], parent[NMAX], dc, nbridges, nbcc;
static std::set<int> bcc[NMAX];
static std::stack<struct pair> edge_stack;
static void dfs(int s)
{
int e, nchld = 0;
low[s] = d[s] = ++dc;
color[s] = GRAY;
for (e = adj[s]; e != 0; e = edges[e].n) {
if (parent[s] != edges[e].v && color[edges[e].v] == GRAY) {
low[s] = min(low[s], low[edges[e].v]);
} else if (color[edges[e].v] == WHITE) {
nchld++;
parent[edges[e].v] = s;
edge_stack.push({s, edges[e].v});
dfs(edges[e].v);
low[s] = min(low[s], low[edges[e].v]);
if (low[edges[e].v] >= d[s]) {
is_art[s] = s != 1 || nchld > 1;
if (is_art[s]) {
while (edge_stack.top().u != s || edge_stack.top().v != edges[e].v) {
bcc[nbcc].insert(edge_stack.top().u);
bcc[nbcc].insert(edge_stack.top().v);
edge_stack.pop();
}
bcc[nbcc].insert(edge_stack.top().u);
bcc[nbcc].insert(edge_stack.top().v);
edge_stack.pop();
nbcc++;
}
}
if (low[edges[e].v] > d[s]) {
bridges[nbridges].u = s;
bridges[nbridges].v = edges[e].v;
nbridges++;
}
}
}
color[s] = BLACK;
}
static void find_art(int n)
{
int i;
for (i = 1; i <= n; i++) {
low[i] = INT_MAX;
}
dfs(1);
i = 0;
while (!edge_stack.empty()) {
i = 1;
bcc[nbcc].insert(edge_stack.top().u);
bcc[nbcc].insert(edge_stack.top().v);
edge_stack.pop();
}
if (i) {
nbcc++;
}
}
int main(void)
{
int n, m, i, u, v;
scanf("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d %d", &u, &v);
edges[2*i].v = u;
edges[2*i].n = adj[v];
adj[v] = 2*i;
edges[2*i+1].v = v;
edges[2*i+1].n = adj[u];
adj[u] = 2*i+1;
}
find_art(n);
//for (i = 1; i <= n; i++) {
//printf("%d: d=%d low=%d\n", i, d[i], low[i]);
//}
//for (i = 1; i <= n; i++) {
//if (is_art[i]) {
//printf("%d ", i);
//}
//}
//printf("\n");
//for (i = 0; i < nbridges; i++) {
//printf("(%d, %d)%c", bridges[i].u, bridges[i].v, " \n"[i == nbridges - 1]);
//}
printf("%d\n", nbcc);
for (i = 0; i < nbcc; i++) {
for (auto it : bcc[i]) {
printf("%d ", it);
}
printf("\n");
}
return 0;
}