Pagini recente » Cod sursa (job #1581301) | Cod sursa (job #2236342) | Cod sursa (job #2600585) | Cod sursa (job #2101518) | Cod sursa (job #1105619)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef vector<int>::iterator it;
typedef pair<int, int> Edge;
const int oo = 0x3f3f3f3f;
const int MAX_N = 100099;
const int NIL = -1;
vector<int> G[MAX_N];
int N, Father[MAX_N], Level[MAX_N], MinLevel[MAX_N];
stack<Edge> Stack;
vector< vector<int> > BC;
vector<Edge> CriticalEdges;
vector<int> CriticalVertices;
template<class T>
inline void EliminateDuplicates(vector<T> &V) {
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
}
inline void DetermineBC(Edge E) {
vector<int> Component;
Edge CurrentE;
do {
CurrentE = Stack.top(); Stack.pop();
Component.push_back(CurrentE.x); Component.push_back(CurrentE.y);
} while (CurrentE != E);
EliminateDuplicates<int>(Component);
BC.push_back(Component);
}
void DFS(int X) {
MinLevel[X] = Level[X];
for (it Y = G[X].begin(); Y != G[X].end(); ++Y) {
if (Father[*Y] != NIL)
continue;
Father[*Y] = X; Level[*Y] = Level[X] + 1;
Stack.push(Edge(X, *Y));
DFS(*Y);
if (MinLevel[*Y] > Level[X])
CriticalEdges.push_back(Edge(X, *Y));
if (MinLevel[*Y] >= Level[X]) {
DetermineBC(Edge(X, *Y));
CriticalVertices.push_back(X);
}
}
bool UsedFather = false;
for (it Y = G[X].begin(); Y != G[X].end(); ++Y) {
if (*Y == Father[X] && !UsedFather)
UsedFather = true;
else
MinLevel[X] = min(MinLevel[X], MinLevel[*Y]);
}
}
void Solve() {
memset(Father, NIL, sizeof(Father));
for (int X = 1; X <= N; ++X) {
if (Father[X] == NIL) {
Father[X] = X; Level[X] = 0;
DFS(X);
}
}
EliminateDuplicates<int>(CriticalVertices);
EliminateDuplicates<Edge>(CriticalEdges);
}
void Read() {
assert(freopen("biconex.in", "r", stdin));
int M; assert(scanf("%d %d", &N, &M) == 2);
for (; M > 0; --M) {
int X, Y; assert(scanf("%d %d", &X, &Y) == 2);
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) {
for (it X = BC[i].begin(); X != BC[i].end(); ++X)
printf("%d ", *X);
printf("\n");
}
}
int main() {
Read();
Solve();
Print();
return 0;
}