Pagini recente » Cod sursa (job #3204343) | Cod sursa (job #2703312) | Cod sursa (job #1244853) | Cod sursa (job #2938487) | Cod sursa (job #2932871)
#include <stdio.h>
#include <vector>
#define MAXN 100005
struct nod {
bool done = false;
int depth = -1;
int anc;
std::vector<int> chd;
};
nod web[MAXN];
std::vector<int> stk;
std::vector<std::vector<int>> comps;
int DFS(int nod, int depth, int par) {
// printf("%d Depth: %d\n", nod, depth);
web[nod].depth = depth;
web[nod].anc = depth;
stk.push_back(nod);
for (int i = 0; i < web[nod].chd.size(); i++) {
if (web[web[nod].chd[i]].depth == -1) {
int val = DFS(web[nod].chd[i], depth + 1, nod);
web[nod].anc = std::min(web[nod].anc, val);
// printf("%d New Edge %d\n", nod, val);
} else if (!web[web[nod].chd[i]].done) {
web[nod].anc = std::min(web[nod].anc, web[web[nod].chd[i]].depth);
// printf("%d Upper Edge %d\n", nod, web[web[nod].chd[i]].depth);
}
}
if (web[nod].anc == web[nod].depth - 1) {
comps.emplace_back();
while(stk.back() != nod) {
comps.back().push_back(stk.back());
web[stk.back()].done = true;
stk.pop_back();
}
comps.back().push_back(nod);
web[nod].done = true;
stk.pop_back();
comps.back().push_back(par);
}
return web[nod].anc;
}
int main() {
FILE *fin, *fout;
int n, m;
int a, b;
int i;
fin = fopen("biconex.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (i = 0; i < m; i++) {
fscanf(fin, "%d%d", &a, &b);
a--;
b--;
web[a].chd.push_back(b);
web[b].chd.push_back(a);
}
fclose(fin);
for (int i = 0; i < n; i++) {
if (!web[i].done) {
DFS(i, 1, -1);
}
}
fout = fopen("biconex.out", "w");
fprintf(fout, "%d\n", (int)comps.size());
for (int i = 0; i < comps.size(); i++) {
for (int j = 0; j < comps[i].size(); j++) {
fprintf(fout, "%d ", comps[i][j] + 1);
}
fprintf(fout, "\n");
}
fclose(fout);
}