Pagini recente » Cod sursa (job #1983148) | Cod sursa (job #257986) | Cod sursa (job #1065026) | Cod sursa (job #1721218) | Cod sursa (job #838275)
Cod sursa(job #838275)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#define x first
#define y second
using namespace std;
typedef vector<int>::iterator vii;
const int MaxN = 100005;
const int MaxE = 200005;
map<pair<int, int>, int> EIndex;
vector<int> G[MaxN];
int N, Level[MaxN], MinLevel[MaxN];
bool CriticalV[MaxN], CriticalE[MaxE];
stack< pair<int, int> > Stack;
vector< vector<int> > BC;
inline void DetermineBC(int X, int Y) {
vector<int> Component;
int NewX, NewY;
do {
NewX = Stack.top().x, NewY = Stack.top().y;
Stack.pop();
Component.push_back(NewX), Component.push_back(NewY);
} while (NewX != X || NewY != Y);
sort(Component.begin(), Component.end());
Component.erase(unique(Component.begin(), Component.end()), Component.end());
BC.push_back(Component);
}
void DFS(int X, int F) {
MinLevel[X] = Level[X];
int NSons = 0;
for (vii Y = G[X].begin(); Y != G[X].end(); ++Y) {
if (Level[*Y] == 0) {
++NSons;
Stack.push(make_pair(X, *Y));
Level[*Y] = Level[X] + 1;
DFS (*Y, X);
if (MinLevel[*Y] > Level[X])
CriticalE[EIndex[make_pair(X, *Y)]] = true;
if (MinLevel[*Y] >= Level[X])
DetermineBC(X, *Y), CriticalV[X] = true;
}
}
bool UsedF = false;
for (vii Y = G[X].begin(); Y != G[X].end(); ++Y) {
if (*Y == F && !UsedF)
UsedF = true;
else
MinLevel[X] = min(MinLevel[X], MinLevel[*Y]);
}
if (X == F)
CriticalV[X] = NSons > 1;
}
void Solve() {
for (int X = 1; X <= N; ++X) {
if (Level[X] == 0) {
Level[X] = 1; DFS(X, X);
}
}
}
void Read() {
assert(freopen("biconex.in", "r", stdin));
int M; assert(scanf("%d %d", &N, &M) == 2);
for (int i = 0; i < M; ++i) {
int X, Y; assert(scanf("%d %d", &X, &Y));
EIndex[make_pair(X, Y)] = EIndex[make_pair(Y, X)] = i;
G[X].push_back(Y), G[Y].push_back(X);
}
}
void Print() {
assert(freopen("biconex.out", "w", stdout));
printf("%d\n", static_cast<int>(BC.size()));
for (size_t i = 0; i < BC.size(); ++i, printf("\n"))
for (vii X = BC[i].begin(); X != BC[i].end(); ++X)
printf("%d ", *X);
}
int main() {
Read();
Solve();
Print();
return 0;
}