Pagini recente » Cod sursa (job #1213133) | Cod sursa (job #1384995) | Cod sursa (job #1446536) | Cod sursa (job #838709) | Cod sursa (job #1847980)
#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];
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;
void dfs(int node, int d, int &low) {
int i = last[node];
depth[node] = d;
viz[node] = true;
while(i != 0) {
if(viz[mc[i]] && depth[mc[i]] < low)
low = depth[mc[i]];
else if(!viz[mc[i]]) {
int up = 1000000000;
dfs(mc[i], d + 1, up);
if(up < low)
low = up;
if(d <= up) {//punct de articulatie
nod[topBic] = node;
bic[topBic++] = comp;
comp++;
}
}
i = next[i];
}
if(d > 1) {
nod[topBic] = node;
bic[topBic++] = comp;
}
}
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]) {
int up = 1000000000;
dfs(i, 1, up);
}
if(last[i] == 0) {
nod[topBic] = i;
bic[topBic++] = comp;
++comp;
viz[i] = true;
}
}
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;
}