Pagini recente » Cod sursa (job #1507028) | Cod sursa (job #2084520) | Cod sursa (job #2343141) | Cod sursa (job #334185) | Cod sursa (job #2213219)
#include <climits>
#include <cstdio>
#include <cstring>
#include <set>
#include <stack>
#include <vector>
#define NMAX 100001
struct pair {
int u, v;
};
static enum c {
WHITE,
GRAY,
BLACK
} color[NMAX];
static std::vector<int> adj[NMAX];
static int low[NMAX], is_art[NMAX], d[NMAX], parent[NMAX], dc, nbcc;
static std::set<int> bcc[NMAX];
static std::stack<struct pair> edge_stack;
static void dfs(int s)
{
int nchld = 0;
low[s] = d[s] = ++dc;
color[s] = GRAY;
for (auto e : adj[s]) {
if (parent[s] != e && color[e] == GRAY) {
low[s] = std::min(low[s], d[e]);
} else if (color[e] == WHITE) {
nchld++;
parent[e] = s;
edge_stack.push({s, e});
dfs(e);
low[s] = std::min(low[s], low[e]);
if (low[e] >= d[s]) {
is_art[s] = s != 1 || nchld > 1;
if (is_art[s]) {
while (edge_stack.top().u != s && edge_stack.top().v != e) {
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++;
}
}
}
}
color[s] = BLACK;
}
static void find_art(int n)
{
int i, f;
for (i = 1; i <= n; i++) {
low[i] = INT_MAX;
}
dfs(1);
f = 0;
while (!edge_stack.empty()) {
f = 1;
bcc[nbcc].insert(edge_stack.top().u);
bcc[nbcc].insert(edge_stack.top().v);
edge_stack.pop();
}
if (f) {
nbcc++;
}
}
int main(void)
{
int n, m, i, u, v;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
while (m--) {
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
find_art(n);
printf("%d\n", nbcc);
for (i = 0; i < nbcc; i++) {
for (auto it : bcc[i]) {
printf("%d ", it);
}
printf("\n");
}
return 0;
}