Pagini recente » Cod sursa (job #720072) | Istoria paginii runda/simulare-oji-matei-1 | Cod sursa (job #2823764) | Cod sursa (job #1637569) | Cod sursa (job #987506)
Cod sursa(job #987506)
#include <cstdio>
#include <utility>
#include <stack>
#include <vector>
#include <algorithm>
#define FILEIN "biconex.in"
#define FILEOUT "biconex.out"
using namespace std;
const int NMAX = 100002;
int N, M;
int lvl[NMAX], low[NMAX], f[NMAX];
vector<int> A[NMAX];
vector< vector<int> > Sol;
stack< pair<int, int> > st;
void dfs( int node ) {
low[node] = lvl[node];
for ( size_t i = 0; i < A[node].size(); i++ )
{
if (f[A[node][i]])
continue;
f[A[node][i]] = node, lvl[A[node][i]] = lvl[node] + 1;
st.push(make_pair(node, A[node][i]));
dfs(A[node][i]);
if (low[A[node][i]] >= lvl[node]) {
vector<int> tmp;
while (st.top().first != node && st.top().second != A[node][i])
tmp.push_back(st.top().first), tmp.push_back(st.top().second), st.pop();
tmp.push_back(node), tmp.push_back(A[node][i]), st.pop();
Sol.push_back(tmp);
}
}
for (size_t i = 0; i < A[node].size(); i++)
if (A[node][i] != f[node])
low[node] = min(low[node], low[A[node][i]]);
}
int main() {
int x, y;
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
scanf("%d %d", &N, &M);
for ( int i = 1; i <= M; i++) {
scanf("%d %d", &x, &y);
A[x].push_back(y);
A[y].push_back(x);
}
for ( int i = 1; i <= N; i++)
if (!f[i])
f[i] = i, dfs(i);
printf("%d\n", Sol.size());
for ( size_t i = 0; i < Sol.size(); i++) {
sort(Sol[i].begin(), Sol[i].end());
printf("%d ", Sol[i][0]);
for ( size_t j = 1; j < Sol[i].size(); j++ ) {
if ( Sol[i][j] != Sol[i][j-1])
printf("%d ", Sol[i][j]);
}
printf("\n");
}
return 0;
}