Pagini recente » Cod sursa (job #2041732) | Cod sursa (job #237134) | Cod sursa (job #1322492) | Cod sursa (job #1467817) | Cod sursa (job #2605835)
#include <bits/stdc++.h>
#define Edge pair<int, int>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
vector<int> adj[kNmax];
vector<int> idx;
vector<int> low_link;
vector<int> parent;
vector<vector<int>> biconex;
void read_input() {
ifstream fin("biconex.in");
fin >> n >> m;
idx = vector<int>(n + 1, -1);
low_link = vector<int>(n + 1, 0);
parent = vector<int> (n + 1, 0);
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
fin.close();
}
void bicx_elem_function() {
int curr_start = 0;
for (int i = 1; i <= n; ++i) {
if (idx[i] == -1) {
parent[i] = 0;
dfs(i, curr_start);
}
}
}
void dfs(int nod, int &curr_start) {
curr_start++;
idx[nod] = curr_start;
low_link[nod] = curr_start;
int children = 0;
for (auto &neigh : adj[nod]) {
if (idx[neigh] == -1) {
parent[neigh] = nod;
children++;
dfs(neigh, curr_start);
low_link[nod] = std::min(low_link[nod], low_link[neigh]);
if (low_link[neigh] >= idx[nod]) {
biconex_function(Edge(nod, neigh));
}
} else {
if (neigh != parent[nod]) {
low_link[nod] = std::min(low_link[nod], idx[neigh]);
}
}
}
}
void biconex_function(Edge edge) {
vector<int> bicx;
Edge curr_edge = Edge(-1, -1);
while(curr_edge != edge) {
bicx.push_back(curr_edge.first);
bicx.push_back(curr_edge.second);
}
sort(bicx.begin(), bicx.end());
auto it = unique(bicx.begin(), bicx.end());
bicx.erase(it, bicx.end());
biconex.push_back(bicx);
}
vector<vector<int>> get_result() {
bicx_elem_function();
/*
TODO: idxi nodurile critice ale grafului neorientat stocat cu liste
de adiacenta in adj.
*/
return biconex;
}
void print_output(const vector<vector<int>>& result) {
ofstream fout("biconex.out");
for (unsigned int i = 0; i < biconex.size(); ++i) {
for (auto &it : biconex[i]) {
fout << it << ' ';
}
fout << '\n';
}
fout.close();
}
};
// Please always keep this simple main function!
int main() {
// Allocate a Task object on heap in order to be able to
// declare huge static-allocated data structures inside the class.
Task *task = new Task();
task->solve();
delete task;
return 0;
}