Pagini recente » Cod sursa (job #106324) | Cod sursa (job #984923) | Cod sursa (job #2804371) | Cod sursa (job #2594977) | Cod sursa (job #2406145)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int kNmax = 100005;
#define MIN(a, b) ((a < b) ? a : b)
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();
}
void tarjan(int u, vector<int>& discovery_time, vector<int>& low,
vector<int>& parent, stack<Edge>& st, vector<vector<Edge>>& sol) {
static int discovered_time = 0;
int children_no = 0;
discovery_time[u] = ++discovered_time;
low[u] = discovered_time;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (discovery_time[v] == -1) {
children_no++;
parent[v] = u;
st.push(Edge(u, v));
tarjan(v, discovery_time, low, parent, st, sol);
low[u] = MIN(low[u], low[v]);
if (((parent[u] == -1) && (children_no > 1)) || ((parent[u] != -1) && (low[v] >= discovery_time[u]))) {
vector<Edge> buffer;
while (st.top().x != u && st.top().y != v) {
buffer.push_back(Edge(st.top()));
st.pop();
}
buffer.push_back(Edge(st.top()));
sol.push_back(buffer);
buffer.clear();
st.pop();
}
}
else if (v != parent[u]) {
low[u] = MIN(low[u], discovery_time[v]);
}
}
// vector<Edge> buffer;
// while (!st.empty()) {
// buffer.push_back(Edge(st.top()));
// st.pop();
// }
// sol.push_back(buffer);
}
vector<vector<Edge>> get_result() {
vector<int> parent(n + 1, -1);
vector<int> low(n + 1);
vector<int> discovery_time(n + 1, -1);
vector<Edge> buffer;
stack<Edge> st;
vector<vector<Edge>> sol;
// cout << "n = " << n << "\n";
// cout << "m = " << m << "\n";
// for (int i = 1; i < n; ++i) {
// cout << "Adj list for node: " << i << " -> ";
// for (int j = 0; j < adj[i].size(); ++j) {
// cout << adj[i][j] << " ";
// }
// cout << "\n";
// }
for (int i = 1; i <=n; ++i) {
if (discovery_time[i] == -1) {
tarjan(i, discovery_time, low, parent, st, sol);
}
}
while (!st.empty()) {
buffer.push_back(Edge(st.top()));
st.pop();
}
sol.push_back(buffer);
return sol;
}
void print_output(const vector<vector<Edge>>& result) {
ofstream fout("biconex.out");
vector<bool> buf(n + 1, false);
fout << result.size() << '\n';
for (int i = 0; i < int(result.size()); i++) {
for (int j = 0; j < result[i].size(); ++j) {
if (buf[result[i][j].x] == false) {
fout << result[i][j].x << " ";
buf[result[i][j].x] = true;
}
if (buf[result[i][j].y] == false) {
fout << result[i][j].y << " ";
buf[result[i][j].y] = true;
}
// fout << result[i][j].x << " " << result[i][j].y << " ";
}
fill(buf.begin(), buf.end(), false);
fout << "\n";
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}