Pagini recente » Rating Vartolomei Vlad (Hatton) | Cod sursa (job #610949) | Cod sursa (job #1650664) | Monitorul de evaluare | Cod sursa (job #2406468)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
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];
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() {
/*
TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
de adiacenta in adj.
*/
vector<vector<int>> sol;
vector<int> idx(n + 1, -1);
vector<int> low(n + 1);
// vector<vector<int>> children(n + 1);
stack<int> stack;
int time = 0;
for (int i = 1; i <= n; ++i) {
if (idx[i] == -1) {
dfs(i, time, idx, low, sol, stack);
}
}
return sol;
}
void dfs(int source, int time, vector<int> &idx, vector<int> &low,
vector<vector<int>> &sol, stack<int> &stack) {
stack.push(source);
idx[source] = time;
low[source] = time;
time++;
for (int x : adj[source]) {
if (idx[x] == -1) {
// children[source].push_back(x);
dfs(x, time, idx, low, sol, stack);
low[source] = min(low[source], low[x]);
if (low[x] >= idx[source]) {
vector<int> CB;
CB.push_back(source);
while (stack.top() != x) {
CB.push_back(stack.top());
stack.pop();
}
CB.push_back(stack.top());
stack.pop();
sol.push_back(CB);
}
} else {
low[source] = min(low[source], idx[x]);
}
}
}
void print_output(vector<vector<int>> result) {
ofstream fout("biconex.out");
fout << result.size() << '\n';
for (auto &x : result) {
for (int y : x) {
fout << y << ' ';
}
fout << '\n';
}
// fout << '\n';
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}