Pagini recente » Cod sursa (job #111220) | Cod sursa (job #1601616) | Cod sursa (job #2165746) | Cod sursa (job #2896435) | Cod sursa (job #499517)
Cod sursa(job #499517)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define pb(a) push_back(a)
int N; // numarul de noduri
vector<vector<int> > G; // graful
stack<pair<int, int> > st; //stackul de muchii
vector<int> dep, low; // depth and low level
vector<vector<int> > B; // biconexele
void biconex(int x, int y) {
vector<int> c;
int nx, ny;
int lst = -1;
do {
nx = st.top().first; ny = st.top().second;
st.pop();
c.pb(ny);
c.pb(nx);
} while (nx != x || ny != y);
sort(c.begin(), c.end());
c = vector<int>(c.begin(), unique(c.begin(), c.end()));
B.pb(c);
}
void dfs(int nod, int parent, int level) {
dep[nod] = low[nod] = level;
for (int i = 0; i < G[nod].size(); ++i) {
int nod2 = G[nod][i];
if (nod2 == parent) continue;
//viziteaza
if (dep[nod2] == -1) {
// pune muchia in stack
st.push(make_pair(nod, nod2));
dfs(nod2, nod, level + 1);
low[nod] = min(low[nod], low[nod2]);
if (low[nod2] >= dep[nod]) biconex(nod, nod2);
} else low[nod] = min(low[nod], low[nod2]);
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int M;
scanf("%d %d", &N, &M);
G.resize(N+1);
while (M--) {
int a, b;
scanf("%d %d", &a, &b);
G[a].pb(b);
G[b].pb(a);
}
dep.assign(N+1, -1);
low.assign(N+1, -1);
dfs(1, 0, 0); //level, parent
printf("%d\n", B.size());
for (int i = 0; i < B.size(); ++i) {
for (int j = 0; j < B[i].size(); ++j)
printf("%d ", B[i][j]);
printf("\n");
}
return 0;
}