Pagini recente » Cod sursa (job #1300209) | Cod sursa (job #2787782) | Cod sursa (job #2376824) | Cod sursa (job #441159) | Cod sursa (job #1095652)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#define x first
#define y second
using namespace std;
typedef vector<int>::iterator it;
typedef pair<int, int> Edge;
const int MAX_N = 100005;
const int NIL = -1;
vector<int> G[MAX_N];
int N, Father[MAX_N], Level[MAX_N], MinLevel[MAX_N];
stack<Edge> Stack;
vector<Edge> CriticalEdges;
vector<int> CriticalVertices;
vector< vector<int> > BiconnectedComponents;
template<class T>
inline void EliminateDuplicates(vector<T> &V)
{
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
}
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(Component);
BiconnectedComponents.push_back(Component);
}
void DFS(int X)
{
int NSons = 0;
MinLevel[X] = Level[X];
for (it Y = G[X].begin(); Y != G[X].end(); ++Y) {
if (Father[*Y] != NIL)
continue;
++NSons;
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]) {
CriticalVertices.push_back(X);
DetermineBC(Edge(X, *Y));
}
}
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]);
}
if (Father[X] == X && NSons > 1)
CriticalVertices.push_back(X);
}
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(CriticalVertices);
EliminateDuplicates(CriticalEdges);
}
inline void AddEdge(int X, int Y)
{
G[X].push_back(Y); G[Y].push_back(X);
}
void Read()
{
freopen("biconex.in", "r", stdin);
int M;
scanf("%d %d", &N, &M);
for (; M > 0; --M) {
int X, Y;
scanf("%d %d", &X, &Y);
AddEdge(X, Y);
}
}
void Print()
{
freopen("biconex.out", "w", stdout);
printf("%d\n", static_cast<int>(BiconnectedComponents.size()));
for (size_t i = 0; i < BiconnectedComponents.size(); ++i) {
for (it X = BiconnectedComponents[i].begin(); X != BiconnectedComponents[i].end(); ++X)
printf("%d ", *X);
printf("\n");
}
}
int main()
{
Read();
Solve();
Print();
return 0;
}