Pagini recente » Cod sursa (job #1257265) | Cod sursa (job #1103779) | Cod sursa (job #2078626) | Cod sursa (job #844462) | Cod sursa (job #628675)
Cod sursa(job #628675)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define MAXN 100100
int idx[MAXN], llink[MAXN];
vector<int> g[MAXN];
vector<vector<int> > comp;
stack<pair<int, int> > stk;
typedef vector<int>::iterator iter;
typedef vector<vector<int> >::iterator viter;
int n, m;
void dfs(int node, int from, int num)
{
idx[node] = llink[node] = num;
for (iter it = g[node].begin(); it != g[node].end(); ++it) {
if (*it != from) {
if (idx[*it] == -1) {
stk.push(make_pair(node, *it));
dfs(*it, node, num + 1);
llink[node] = min(llink[node], llink[*it]);
if (llink[*it] >= idx[node]) {
vector<int> c;
int x, y;
do {
x = stk.top().first;
y = stk.top().second;
stk.pop();
c.push_back(x);
c.push_back(y);
} while (x != node || y != *it);
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
comp.push_back(c);
}
} else {
llink[node] = min(llink[node], idx[*it]);
}
}
}
}
int main()
{
fstream fin("biconex.in", ios::in);
fstream fout("biconex.out", ios::out);
fin >> n >> m;
for (int i = 1; i <= n; ++i) {
idx[i] = -1;
}
for (int i = 0, x, y; i < m; ++i) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0, 0);
fout << comp.size() << endl;
for (viter it = comp.begin(); it != comp.end(); ++it) {
for (iter jt = it->begin(); jt != it->end(); ++jt) {
fout << *jt << " ";
}
fout << endl;
}
fin.close();
fout.close();
return 0;
}