Pagini recente » Cod sursa (job #3264953) | Cod sursa (job #2821141) | Cod sursa (job #2664980) | Cod sursa (job #2622443) | Cod sursa (job #1539161)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
const int MAX_M = 200000;
const int NIL = -1;
struct cell {
int v;
int next;
};
cell l[2 * MAX_M];
int adj[MAX_N];
int dfn[MAX_N];
int nextIndex;
int st[2 * MAX_N];
int ss;
vector <vector <int> > BCC;
int N;
void biconex(int u, int v) {
vector <int> tmp;
do {
ss--;
tmp.emplace_back(st[2 * ss]);
tmp.emplace_back(st[2 * ss + 1]);
} while (st[2 * ss] != u || st[2 * ss + 1] != v);
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
BCC.emplace_back(tmp);
}
int dfs(int u) {
int v, minPtr, minPtrV;
dfn[u] = minPtr = nextIndex++;
for (int i = adj[u]; i != NIL; i = l[i].next) {
v = l[i].v;
if (dfn[v] == NIL) {
st[2 * ss] = u;
st[2 * ss + 1] = v;
ss++;
minPtrV = dfs(v);
minPtr = min(minPtr, minPtrV);
if (minPtrV >= dfn[u]) {
biconex(u, v);
}
} else {
minPtr = min(minPtr, dfn[v]);
}
}
return minPtr;
}
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
int main(void) {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int M;
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++) {
adj[i] = dfn[i] = NIL;
}
for (int i = 0; i < M; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u - 1, v - 1, 2 * i);
addEdge(v - 1, u - 1, 2 * i + 1);
}
fclose(stdin);
dfs(0);
printf("%lu\n", BCC.size());
for (auto v : BCC) {
for (auto q : v) {
printf("%d ", 1 + q);
}
putchar('\n');
}
fclose(stdout);
return 0;
}