Pagini recente » Cod sursa (job #2956622) | Cod sursa (job #2970415) | Cod sursa (job #2557337) | Cod sursa (job #1964792) | Cod sursa (job #2886808)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int NMAX = 1e5, NOTVIS = 1e9;
struct edge {
int nd1, nd2;
};
vector<vector<int>> bi;
vector<int> adj[NMAX + 1];
edge stk[NMAX + 1];
int h[NMAX + 1], father[NMAX + 1], sp;
int findBi(int nd);
void pushBi(edge e);
int main() {
int n, m, nd1, nd2;
FILE *fin = fopen("biconex.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (int i = 0; i < m; i++) {
fscanf(fin, "%d%d", &nd1, &nd2);
adj[nd1].push_back(nd2);
adj[nd2].push_back(nd1);
}
fclose(fin);
for (int i = 0; i <= n; i++)
h[i] = NOTVIS;
h[1] = 0, father[1] = 0;
findBi(1);
FILE *fout = fopen("biconex.out", "w");
fprintf(fout, "%d\n", bi.size());
for (vector<int> curr: bi) {
for (int nd: curr)
fprintf(fout, "%d ", nd);
fprintf(fout, "\n");
}
fclose(fout);
return 0;
}
int findBi(int nd) {
int reach = h[nd];
for (int nxt: adj[nd])
if (h[nxt] == NOTVIS) {
h[nxt] = h[nd] + 1;
stk[++sp] = {nd, nxt};
father[nxt] = nd;
reach = min(reach, findBi(nxt));
}
else if (nxt != father[nd])reach = min(reach, h[nxt]);
if (reach >= h[father[nd]])
pushBi({father[nd], nd});
return reach;
}
void pushBi(edge e) {
vector<int> currBi;
while (sp > 0 && (stk[sp].nd1 != e.nd1 || stk[sp].nd2 != e.nd2))
currBi.push_back(stk[sp--].nd2);
currBi.push_back(stk[sp].nd2);
currBi.push_back(stk[sp--].nd1);
bi.push_back(currBi);
}