Pagini recente » Cod sursa (job #1037202) | Cod sursa (job #921119) | Cod sursa (job #2350709) | Cod sursa (job #2199980) | Cod sursa (job #1166786)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
static const int NIL = -1;
vector< vector<int> > G, Components;
int V;
vector<int> Level, MinLevel, CriticalVertices;
vector< pair<int, int> > CriticalEdges;
stack< pair<int, int> > EdgeStack;
template<class Type>
inline void EraseDuplicates(vector<Type> &v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
inline void GetComponent(const pair<int, int> &edge) {
pair<int, int> topEdge;
vector<int> component;
do {
topEdge = EdgeStack.top();
EdgeStack.pop();
component.push_back(topEdge.first);
component.push_back(topEdge.second);
} while (topEdge != edge);
EraseDuplicates<int>(component);
Components.push_back(component);
}
void DFS(const int x, const int father) {
MinLevel[x] = Level[x];
for (vector<int>::const_iterator y = G[x].begin(); y != G[x].end(); ++y) {
if (Level[*y] != -1)
continue;
Level[*y] = Level[x] + 1;
EdgeStack.push(make_pair(x, *y));
DFS(*y, x);
if (MinLevel[*y] > Level[x])
CriticalEdges.push_back(make_pair(x, *y));
if (MinLevel[*y] >= Level[x]) {
CriticalVertices.push_back(x);
GetComponent(make_pair(x, *y));
}
}
bool usedFather = false;
for (vector<int>::const_iterator y = G[x].begin(); y != G[x].end(); ++y) {
if (!usedFather && *y == father)
usedFather = true;
else
MinLevel[x] = min(MinLevel[x], MinLevel[*y]);
}
}
void Solve() {
Level = MinLevel = vector<int>(V, -1);
for (int x = 0; x < V; ++x) {
if (Level[x] == -1) {
Level[x] = 0;
DFS(x, NIL);
}
}
EraseDuplicates<int>(CriticalVertices);
EraseDuplicates< pair<int, int> >(CriticalEdges);
}
inline void AddEdge(const int x, const int y) {
G[x].push_back(y);
G[y].push_back(x);
}
void Read() {
ifstream cin("biconex.in");
int E;
cin >> V >> E;
G = vector< vector<int> >(V, vector<int>());
for (; E > 0; --E) {
int x, y;
cin >> x >> y;
AddEdge(x - 1, y - 1);
}
cin.close();
}
void Print() {
ofstream cout("biconex.out");
cout << int(Components.size()) << "\n";
for (int i = 0; i < int(Components.size()); ++i) {
for (vector<int>::const_iterator x = Components[i].begin(); x != Components[i].end(); ++x)
cout << *x + 1 << " ";
cout << "\n";
}
cout.close();
}
int main() {
Read();
Solve();
Print();
return 0;
}