Pagini recente » Cod sursa (job #2764509) | Cod sursa (job #2205319) | Cod sursa (job #3219083) | Cod sursa (job #2695935) | Cod sursa (job #2603385)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <iostream>
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];
struct Edge {
int x;
int y;
Edge(int _x, int _y) : x(_x), y(_y) {}
};
void read_input() {
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);
}
fin.close();
}
vector<vector<int>> get_result() {
/*
Componenetele biconexe ale unui graf
adj[i] = lista de adiacenta a nodului i
*/
vector<vector<int>> sol; // vectorul de solutii
stack<int> bx; // stiva de noduri
vector<int> parent(n + 1); // vector de parinti
int timp = 0;
vector<int> idx(n + 1);
vector<int> low(n + 1);
for (int i = 1; i <= n; i++) {
idx[i] = -1;
}
for (int v = 1; v <= n; v++) {
if (idx[v] == -1) {
dfsCV(v, idx, low, timp, parent, sol, bx);
}
}
return sol;
}
void dfsCV(int v, vector<int> &idx, vector<int> &low, int &timp,
vector<int> &parent, vector<vector<int>> &sol, stack<int> &bx) {
idx[v] = low[v] = timp;
timp++;
vector<int> children;
bx.push(v); // adaug nodul din care se face dfs intr-o stiva
for (int u : adj[v]) {
if (idx[u] == -1) {
children.push_back(u);
parent[u] = v;
dfsCV(u, idx, low, timp, parent, sol, bx);
if (low[v] > low[u]) {
low[v] = low[u];
}
if (low[u] >= idx[v]) { // am gasit un punct de articulatie
vector<int> comp;
while (bx.top() != v) { // elimin din stiva nodurile
comp.push_back(bx.top()); // pana la punctul de articulatie gasit
bx.pop(); // reprezentand componenta biconexa
}
comp.push_back(bx.top());
sol.push_back(comp);
comp.clear();
}
}
else {
if (u != parent[v]) {
if (low[v] > idx[u])
low[v] = idx[u];
}
}
}
}
void print_output(vector<vector<int>> result) {
ofstream fout("biconex.out");
fout << result.size() << '\n';
for (const auto& ctc : result) {
for (int nod : ctc) {
fout << nod << ' ';
}
fout << '\n';
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}