Pagini recente » Cod sursa (job #745074) | Monitorul de evaluare | Cod sursa (job #1031755) | Cod sursa (job #3144540) | Cod sursa (job #1751269)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100005;
struct PII {
int x, y;
inline PII() { }
inline PII(int _x, int _y) {
x = _x;
y = _y;
}
};
vector<PII> stk;
int ant;
vector<int> g[NMAX],
bix[NMAX];
bool art[NMAX],
gws[NMAX];
int low[NMAX],
lvl[NMAX];
void add(int lst) {
PII top;
do {
top = stk.back();
bix[ant].push_back(top.y);
stk.pop_back();
} while(top.x != lst);
bix[ant].push_back(lst);
++ant;
}
void dfs(int u, int p) {
lvl[u] = lvl[p] + 1;
low[u] = lvl[p] + 1;
gws[u] = true;
for(int v: g[u]) if(v != p) {
if(gws[v]) {
low[u] = min(low[u], lvl[v]);
}
else {
stk.push_back( PII(u, v) );
dfs(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= lvl[u]) {
art[u] = true;
add(u);
}
}
}
}
int main(void) {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m, x, y;
scanf("%d%d", &n, &m);
while(m--) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1; i <= n; ++i)
if(!gws[i])
dfs(i, 0);
printf("%d\n", ant);
for(int i=0; i<ant; ++i) {
for(auto j:bix[i])
printf("%d ", j);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}