Pagini recente » Cod sursa (job #939252) | Cod sursa (job #1299466) | Cod sursa (job #1679400) | Cod sursa (job #2243658) | Cod sursa (job #2596153)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>
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();
}
void dfs(vector<vector<int>>& sol, vector<int>& idx, vector<int>& low,
int& index, int node, int parent, stack<pair<int, int>>& edges) {
idx[node] = index;
low[node] = index;
index++;
for (int i = 0; i < (int)adj[node].size(); ++i) {
if (!idx[adj[node][i]]) {
edges.push(pair<int, int>(node, adj[node][i]));
dfs(sol, idx, low, index, adj[node][i], node, edges);
low[node] = min(low[node], low[adj[node][i]]);
if (low[adj[node][i]] >= idx[node]) {
vector<int> new_solution;
int x, y;
new_solution.emplace_back(edges.top().second);
do {
x = edges.top().first;
y = edges.top().second;
new_solution.emplace_back(x);
edges.pop();
} while (x != node || y != adj[node][i]);
sol.emplace_back(new_solution);
}
} else {
if (parent != adj[node][i]) {
low[node] = min(low[node], idx[adj[node][i]]);
}
}
}
}
vector<vector<int>> get_result() {
vector<int> idx(n + 1, 0);
vector<int> low(n + 1, 0);
int index = 1;
vector<vector<int>> sol;
stack<pair<int, int>> edges;
for (int i = 1; i <= n; ++i) {
if (!idx[i]) {
dfs(sol, idx, low, index, i, 0, edges);
}
}
return sol;
}
void print_output(vector<vector<int>> result) {
ofstream fout("biconex.out");
fout << result.size() << '\n';
for (int i = 0; i < (int)result.size(); ++i) {
for (int j = 0; j < (int)result[i].size(); ++j) {
fout << result[i][j] << ' ';
}
fout << '\n';
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}