Pagini recente » Cod sursa (job #106669) | Cod sursa (job #3001418) | Cod sursa (job #2289616) | Cod sursa (job #2511102) | Cod sursa (job #1451533)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <algorithm>
using namespace std;
#define NMAX 100100
#define UNDEFINED 0
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> graph[NMAX];
vector<vector<int> > solution;
stack<pair<int, int> > s;
int idx[NMAX];
int lowlink[NMAX];
int parent[NMAX];
int index, nodes;
inline void initParent() {
for (int i = 0; i < nodes; i++)
parent[i] = -1;
}
inline void printSolution() {
vector<int> sol;
while (!s.empty()) {
sol.push_back(s.top().first);
sol.push_back(s.top().second);
s.pop();
}
solution.push_back(sol);
out << solution.size() << "\n";
for (unsigned int i = 0; i < solution.size(); i++) {
sort(solution[i].begin(), solution[i].end());
solution[i].erase(unique(solution[i].begin(), solution[i].end()), solution[i].end());
for (unsigned int j = 0; j < solution[i].size(); j++) {
out << solution[i].at(j) + 1 << " ";
}
out << "\n";
}
}
inline void addSolution(pair<int, int> p) {
vector<int> sol;
while (s.top() != p) {
sol.push_back(s.top().first);
sol.push_back(s.top().second);
s.pop();
}
sol.push_back(s.top().first);
sol.push_back(s.top().second);
s.pop();
solution.push_back(sol);
}
void dfsAp(int start) {
index++;
int children = 0;
idx[start] = lowlink[start] = index;
for (unsigned int i = 0; i < graph[start].size(); i++) {
int neighbour = graph[start].at(i);
if (idx[neighbour] == UNDEFINED) {
s.push(make_pair(start, neighbour));
children++;
parent[neighbour] = start;
dfsAp(neighbour);
lowlink[start] = min(lowlink[start], lowlink[neighbour]);
if (parent[start] == -1 && children > 1) {
addSolution(make_pair(start, neighbour));
}
if (parent[start] != -1 && lowlink[neighbour] >= idx[start]) {
addSolution(make_pair(start, neighbour));
}
}
else if (neighbour != parent[start]) {
lowlink[start] = min(lowlink[start], idx[neighbour]);
}
}
}
void ArticulationPoints() {
initParent();
index = 0;
for (int i = 0; i < nodes; i++) {
if (idx[i] == UNDEFINED)
dfsAp(i);
}
printSolution();
}
int main() {
int edges, x, y;
in >> nodes >> edges;
for (int i = 0; i < edges; i++) {
in >> x >> y;
graph[x - 1].push_back(y - 1);
graph[y - 1].push_back(x - 1);
}
ArticulationPoints();
return 0;
}