Pagini recente » Cod sursa (job #671504) | Cod sursa (job #1340984) | Cod sursa (job #1300568) | Cod sursa (job #2897946) | Cod sursa (job #1392942)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#define NMAX 100008
using namespace std;
int n, m;
vector<int> v[NMAX];
int depth[NMAX], lowp[NMAX], nrDfs;
stack<pair<int, int> > st;
vector<int> sol[NMAX];
int nrComp;
set<int> auxSol;
void read()
{
scanf("%d %d\n", &n, &m);
int x, y;
for (int i = 1; i <= m; ++i) {
scanf("%d %d\n", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
depth[i] = lowp[i] = -1;
}
}
void dfs(int x, int p) /// p -> x
{
int y;
depth[x] = lowp[x] = nrDfs++;
for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it) {
y = (*it);
if (y != p && depth[y] < depth[x])
st.push(make_pair(x, y));
if (depth[y] == -1) {
dfs(y, x);
lowp[x] = min(lowp[x], lowp[y]);
if (depth[x] <= lowp[y]) {
/// salvare solutie
if (st.top().first == x && st.top().second == y)
sol[nrComp].push_back(st.top().second);
sol[nrComp].push_back(st.top().first);
while (st.top().first != x || st.top().second != y) {
st.pop();
sol[nrComp].push_back(st.top().first);
}
st.pop();
++nrComp;
}
} else if (y != p) {
lowp[x] = min(lowp[x], depth[y]);
}
}
}
void write()
{
printf("%d\n", nrComp);
for (int i = 0; i < nrComp; ++i) {
for (int j = 0; j < sol[i].size(); ++j)
auxSol.insert(sol[i][j]);
for (set<int>::iterator it = auxSol.begin(); it != auxSol.end(); ++it)
printf("%d ", (*it));
auxSol.clear();
printf("\n");
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
read();
dfs(1, -1);
write();
return 0;
}