Pagini recente » Cod sursa (job #792681) | Cod sursa (job #2054270) | Cod sursa (job #907349) | Cod sursa (job #1158533) | Cod sursa (job #449005)
Cod sursa(job #449005)
#include <stdio.h>
#include <vector>
#include <bitset>
#include <algorithm>
#include <set>
using namespace std;
#define maxN 100100
#define ROOT 1
#define oo 100100
#define maxM 200100
bitset <maxN> viz, art_point;
vector <int> G[maxN];
set <int> Sol_vec[maxM];
vector < pair <int, int> > stack;
int nivel[maxN], low[maxN], N, M, cate_ramase, Sol, Nr;
void df (int nod, int parinte) {
int niv_min = oo;
viz[nod] = 1; nivel[nod] = nivel[parinte] + 1;
cate_ramase --;
low[nod] = nivel[nod];
for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it) {
if (*it == parinte || (viz[*it] && nivel[*it] > nivel[nod]))
continue;
if (viz[*it]) {
low[nod] = min(low[nod], nivel[*it]);
stack.push_back(make_pair(nod, *it));
} else {
stack.push_back(make_pair(nod, *it));
df(*it, nod);
niv_min = min(niv_min, low[*it]);
if (low[*it] >= nivel[nod] && nod != ROOT) {
art_point[nod] = 1;
// fprintf(stderr, "art_point = %d\n", nod);
++ Nr;
for (; stack.back() != make_pair(nod, *it); stack.pop_back()) {
Sol_vec[Nr].insert(stack.back().first);
Sol_vec[Nr].insert(stack.back().second);
// fprintf(stderr, "%d %d\n", stack.back().first, stack.back().second);
}
Sol_vec[Nr].insert(stack.back().first);
Sol_vec[Nr].insert(stack.back().second);
stack.pop_back();
}
}
if (nod == ROOT && cate_ramase > 0) {
art_point[ROOT] = 1;
++ Nr;
for (; stack.back() != make_pair(nod, *it); stack.pop_back()) {
Sol_vec[Nr].insert(stack.back().first);
Sol_vec[Nr].insert(stack.back().second);
}
Sol_vec[Nr].insert(stack.back().first);
Sol_vec[Nr].insert(stack.back().second);
stack.pop_back();
}
}
low[nod] = min(low[nod], niv_min);
}
int main () {
int i, a, b, j;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &N, &M);
for (i = 1; i <= M; ++ i) {
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
cate_ramase = N;
df(ROOT, 0);
if (stack.size()) {
++ Nr;
for (; stack.size(); stack.pop_back()) {
Sol_vec[Nr].insert(stack.back().first);
Sol_vec[Nr].insert(stack.back().second);
}
}
printf("%d\n", Nr);
for (i = 1; i <= Nr; ++ i) {
for (set <int> :: iterator it = Sol_vec[i].begin(); it != Sol_vec[i].end(); ++ it)
printf("%d ", *it);
puts("");
}
}