Pagini recente » Cod sursa (job #1738347) | Cod sursa (job #2153387) | Cod sursa (job #2238673) | Cod sursa (job #617832) | Cod sursa (job #1848089)
#include <cstdio>
const int MAX_N = 100000;
const int MAX_M = 200000;
int last[1+MAX_N], mc[1+2*MAX_M], next[1+2*MAX_M], depth[1+MAX_N], low[1+MAX_N];
bool viz[1+MAX_N];
inline void addM(int a, int b, int id) {
next[id] = last[a];
mc[id] = b;
last[a] = id;
}
int comp, nod[2*MAX_N], bic[2*MAX_N], topBic;
int ma[MAX_M], mb[MAX_M], top;
void dfs(int node, int d, int papa) {
int i = last[node];
depth[node] = d;
low[node] = d;
viz[node] = true;
while(i != 0) {
if(mc[i] != papa) {
if(!viz[mc[i]]) {
dfs(mc[i], d + 1, node);
if(low[mc[i]] < low[node])
low[node] = low[mc[i]];
if(d <= low[mc[i]]) {
comp++;
}
} else if(low[mc[i]] < low[node])
low[node] = low[mc[i]];
}
i = next[i];
}
}
int main() {
int n, m, a, b;
FILE *fin = fopen("biconex.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(int i = 1; i <= m; ++i) {
fscanf(fin, "%d%d", &a, &b);
addM(a, b, i * 2 - 1);
addM(b, a, i * 2);
}
fclose(fin);
for(int i = 1; i <= n; ++i)
if(!viz[i])
dfs(i, 1, 0);
FILE *fout = fopen("biconex.out", "w");
fprintf(fout, "%d\n", comp);
int last = bic[0];
for(int i = 0; i < topBic; ++i) {
if(bic[i] == last)
fprintf(fout, "%d ", nod[i]);
else {
fprintf(fout, "\n%d ", nod[i]);
last = bic[i];
}
}
fclose(fout);
return 0;
}