Pagini recente » Cod sursa (job #3293964) | Cod sursa (job #57) | Cod sursa (job #3256262) | Cod sursa (job #3247281) | Cod sursa (job #2930247)
#include <stdio.h>
#include <vector>
#define MAXN 100005
struct nod {
bool viz = false;
int depth = 0;
std::vector<int> chd;
};
struct stk_elem {
int nod;
int anc;
};
nod web[MAXN];
std::vector<stk_elem> stk;
std::vector<std::vector<int>> comps;
int DFS(int nod, int depth) {
//printf("%d Depth: %d\n", nod, depth);
web[nod].depth = depth;
stk.push_back({nod, depth});
for (int i = 0; i < web[nod].chd.size(); i++) {
if (web[web[nod].chd[i]].depth) {
stk.back().anc = std::min(stk.back().anc, web[web[nod].chd[i]].depth);
//printf("%d Upper Edge %d\n", nod, web[web[nod].chd[i]].depth);
}
else if (!web[web[nod].chd[i]].viz) {
int val = DFS(web[nod].chd[i], depth + 1);
stk.back().anc = std::min(stk.back().anc, val);
//printf("%d New Edge %d\n", nod, val);
}
}
int ret = stk.back().anc;
stk.pop_back();
if (!stk.empty()) {
if (stk.size() == ret) {
comps.back().push_back(nod);
comps.back().push_back(stk.back().nod);
comps.emplace_back();
//printf("%d New component %d\n", nod, ret);
}
else {
comps.back().push_back(nod);
//printf("%d Added %d %d\n", nod, (int)stk.size(), ret);
}
}
web[nod].depth = 0;
web[nod].viz = true;
return ret;
}
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].viz) {
comps.emplace_back();
DFS(i, 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);
}