Pagini recente » Cod sursa (job #1716615) | Cod sursa (job #3184696) | Cod sursa (job #453043) | Cod sursa (job #260014) | Cod sursa (job #2610014)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <algorithm>
using namespace std;
#define NMAX 100002
class Task {
std::vector<int> matrix[NMAX];
std::vector<int> index;
std::vector<int> low;
std::vector<int> parent;
std::stack<std::pair <int, int>> sc;
std::vector<std::vector<int>> biconex;
int ctime;
int N;
int M;
void read_input() {
std::ifstream in("biconex.in");
in >> N;
index = std::vector<int> (N + 1, -1);
low = std::vector<int> (N + 1);
parent = std::vector<int> (N + 1, -1);
ctime = 0;
in >> M;
for (int i = 0; i < M; i++) {
int x, y;
in >> x >> y;
matrix[x].push_back(y);
matrix[y].push_back(x);
}
in.close();
}
void show_matrix() {
for (int i = 0; i < N; i++) {
std::cout<<i<<":";
for (int j = 0; j < matrix[i].size(); j++) {
std::cout<<matrix[i][j]<<" ";
}
std::cout<<"\n";
}
}
void get_biconnex_components() {
for (int i = 1; i <= N; i++) {
if (index[i] == -1) {
biconex_component_tarjan(i);
parent[i] = 0;
}
}
}
void biconex_component_tarjan(int node) {
index[node] = ctime;
low[node] = ctime;
ctime++;
int children = 0;
for (auto const &neight : matrix[node]) {
if (index[neight] == -1) {
parent[neight] = node;
children++;
sc.push ({node, neight});
biconex_component_tarjan(neight);
low[node] = std::min (low[node], low[neight]);
if (low[neight] >= index[node]) {
get_biconnex({node, neight});
}
} else {
if (neight != parent[node]) {
low[node] = std::min(low[node], index[neight]);
}
}
}
}
void get_biconnex(std::pair<int, int> target_edge) {
std::vector<int> bcc;
std::pair<int, int> edge = {-1, -1};
while (edge != target_edge) {
edge = sc.top();
bcc.push_back(edge.first);
bcc.push_back(edge.second);
sc.pop();
std::sort(bcc.begin(), bcc.end());
auto it = std::unique(bcc.begin(), bcc.end());
bcc.erase(it, bcc.end());
}
biconex.push_back(bcc);
}
void print() {
std::ofstream out("biconex.out");
out<<biconex.size()<<"\n";
for (auto const &vector : biconex) {
for (auto const &elem : vector) {
out<<elem <<" ";
}
out<<"\n";
}
out.close();
return;
}
public:
void solve() {
read_input();
get_biconnex_components();
print();
}
};
int main() {
Task* task = new Task();
task->solve();
delete(task);
return 0;
}