Pagini recente » Cod sursa (job #2205864) | Cod sursa (job #321784) | Rating Stefan catalin (virtualdj495) | Cod sursa (job #1565529) | Cod sursa (job #1539169)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N = 100000;
const int MAX_M = 200000;
const int NIL = -1;
const int BUFFSIZE = 65536;
char buff[BUFFSIZE];
int pos = 0;
inline void PutChar(const char &c) {
buff[pos++] = c;
if (pos == BUFFSIZE) {
fwrite(buff, 1, BUFFSIZE, stdout);
pos = 0;
}
}
inline void PrintInteger(int x) {
char digs[8];
int n = 0, q;
do {
q = x / 10;
digs[n++] = x - q * 10 + '0';
x = q;
} while (x != 0);
while (n--) {
PutChar(digs[n]);
}
}
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;
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 N, 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);
PrintInteger(BCC.size());
PutChar('\n');
for (auto v : BCC) {
for (auto q : v) {
PrintInteger(1 + q);
PutChar(' ');
}
PutChar('\n');
}
fwrite(buff, 1, pos, stdout);
fclose(stdout);
return 0;
}