Pagini recente » Cod sursa (job #2809806) | Cod sursa (job #433160) | Cod sursa (job #1692573) | Cod sursa (job #265186) | Cod sursa (job #2609999)
#include <bits/stdc++.h>
const int kNmax = 100005;
struct Edge {
int x;
int y;
};
class Task {
public:
void solve() {
read_input();
get_result();
print_output();
}
private:
int n;
int m;
std::vector<int> adj[kNmax];
std::vector<std::vector<int>> allBiconexComps;
int time;
void read_input() {
std::ifstream fin("biconex.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
time = 0;
fin.close();
}
void get_result() {
std::vector<int> idx(n + 1, 0);
std::vector<int> low (n + 1, INT_MIN);
std::unordered_map<int, int> parent;
std::stack<struct Edge> helperStack;
for (int i = 1; i <= n; i++) {
if (idx[i] == 0) {
dfsHelper(i, idx, low, parent, helperStack);
}
}
}
void dfsHelper(int node, std::vector<int> &idx, std::vector<int> &low,
std::unordered_map<int, int> &parent, std::stack<struct Edge> &helperStack) {
time++;
idx[node] = time;
low[node] = time;
int numberOfChildren = 0;
for (auto &adj : adj[node]) {
if (idx[adj] == 0) {
struct Edge newEdge;
newEdge.x = node;
newEdge.y = adj;
helperStack.push(newEdge);
parent[adj] = node;
numberOfChildren++;
dfsHelper(adj, idx, low, parent, helperStack);
low[node] = std::min(low[node], low[adj]);
if (low[adj] >= idx[node]) {
getBiconexComp(newEdge, helperStack);
}
} else {
if (parent.find(node) != parent.end()) {
if (adj!= parent[node]) {
low[node] = std::min(low[node], idx[adj]);
}
}
}
}
}
void getBiconexComp(struct Edge &targetEdge, std::stack<struct Edge> &helperStack) {
std::set<int> newBiconexComp;
struct Edge currEdge;
while (currEdge.x != targetEdge.x || currEdge.y != targetEdge.y) {
currEdge = helperStack.top();
newBiconexComp.insert(currEdge.x);
newBiconexComp.insert(currEdge.y);
helperStack.pop();
}
allBiconexComps.push_back(std::vector<int>(newBiconexComp.begin(), newBiconexComp.end()));
}
void print_output() {
std::ofstream fout("biconex.out");
fout << allBiconexComps.size() << "\n";
for (int i = 0; i < allBiconexComps.size(); i++) {
for (auto& elem : allBiconexComps[i]) {
fout << elem << " ";
}
fout << "\n";
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}