Pagini recente » Cod sursa (job #2874291) | Cod sursa (job #384871) | Cod sursa (job #1396322) | Cod sursa (job #2089258) | Cod sursa (job #2198720)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define pii pair<int, int>
#define mk make_pair
#define MAX 100005
using namespace std;
int n, m, x, y;
int low[MAX], d[MAX];
vector<int> l[MAX], c;
vector<vector<int> > bic;
stack<pii> edges;
void biconex(int x, int p, int depth) {
d[x] = low[x] = depth;
for(int i = 0; i < l[x].size(); ++i) {
if(l[x][i] == p)
continue;
if(!d[l[x][i]]) {
edges.push(mk(x, l[x][i]));
biconex(l[x][i], x, depth + 1);
low[x] = min(low[x], low[l[x][i]]);
if(depth <= low[l[x][i]]) {
int p1, p2;
c.clear();
do {
p1 = edges.top().first;
p2 = edges.top().second;
edges.pop();
c.push_back(p2);
} while(p1 != x || p2 != l[x][i]);
c.push_back(p1);
bic.push_back(c);
}
}
else
low[x] = min(low[x], d[l[x][i]]);
}
}
int main() {
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> n >> m;
for(int i = 0; i < m; ++i) {
f >> x >> y;
l[x].push_back(y);
l[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!low[i])
biconex(i, 0, 1);
g << bic.size() << "\n";
for(int i = 0; i < bic.size(); ++i) {
sort(bic[i].begin(), bic[i].end());
for(int j = 0; j < bic[i].size(); ++j)
g << bic[i][j] << " ";
g << "\n";
}
return 0;
}