Pagini recente » Cod sursa (job #2404149) | Cod sursa (job #216042) | Cod sursa (job #2047272) | Cod sursa (job #610656) | Cod sursa (job #447683)
Cod sursa(job #447683)
#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], Set_biconex[maxN];
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]);
} else {
df(*it, nod);
niv_min = min(niv_min, low[*it]);
if (low[*it] >= nivel[nod] && nod != ROOT)
art_point[nod] = 1;
}
if (nod == ROOT && cate_ramase > 0)
art_point[ROOT] = 1;
}
low[nod] = min(low[nod], niv_min);
}
void df2 (int nod) {
//fprintf(stderr, "%d ", nod);
Sol_vec[Nr].insert(nod);
if (art_point[nod] == 1) {
Set_biconex[nod].insert(Nr);
return;
}
viz[nod] = 1;
for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it)
if (! viz[*it])
df2(*it);
}
bool set_intersect (int i, int j) {
if (Set_biconex[i].size() > Set_biconex[j].size())
swap(i, j);
for (set <int> :: iterator it = Set_biconex[i].begin(); it != Set_biconex[i].end(); ++ it)
if (Set_biconex[j].find(*it) != Set_biconex[j].end())
return true;
return false;
}
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);
viz.reset();
for (i = 1; i <= N; ++ i)
if (! art_point[i] && ! viz[i]) {
++ Nr;
df2(i);
// fprintf(stderr, "\n");
}
for (i = 1; i <= N; ++ i)
if (art_point[i] == 1)
for (vector <int> :: iterator it = G[i].begin(); it != G[i].end(); ++ it)
if (art_point[*it] && *it > i && ! set_intersect (i, *it)) {
++ Nr;
Sol_vec[Nr].insert(i);
Sol_vec[Nr].insert(*it);
}
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("");
}
}