Pagini recente » Cod sursa (job #2391597) | Cod sursa (job #78456) | Cod sursa (job #647897) | Cod sursa (job #2089385) | Cod sursa (job #3223301)
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>
#include <algorithm>
int32_t min(int32_t x, int32_t y) {
return (x < y) ? x : y;
}
const int32_t MAX_N = 100000;
const int32_t MAX_M = 200000;
struct Edge {
int32_t x, y;
};
std::vector<int32_t> adj[MAX_N];
int32_t depths[MAX_N], low[MAX_N];
Edge stack[MAX_N]; int32_t top;
std::vector<int32_t> comps[MAX_N]; int32_t count;
void DFS(int32_t node, int32_t prev, int32_t depth) {
depths[node] = depth;
low[node] = depth;
for(int32_t next : adj[node]) {
if(next == prev)
continue;
if(depths[next] == -1) {
stack[top++] = { node, next };
DFS(next, node, depth + 1);
low[node] = min(low[node], low[next]);
if(low[next] >= depth) {
do {
comps[count].push_back(stack[top - 1].x);
comps[count].push_back(stack[top - 1].y);
--top;
} while(stack[top].x != node || stack[top].y != next);
std::sort(comps[count].begin(), comps[count].end());
comps[count].erase(std::unique(comps[count].begin(), comps[count].end()), comps[count].end());
++count;
}
} else {
low[node] = min(low[node], depths[next]);
}
}
}
int main() {
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
int32_t n, m;
fin >> n >> m;
for(int32_t i = 0; i != m; ++i) {
int32_t x, y;
fin >> x >> y;
--x; --y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for(int32_t i = 0; i != n; ++i)
depths[i] = -1;
DFS(0, -1, 0);
fout << count << '\n';
for(int32_t i = 0; i != count; ++i) {
for(int32_t node : comps[i])
fout << (node + 1) << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}