Pagini recente » Cod sursa (job #1696366) | Cod sursa (job #2474501) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2199528)
#include <bits/stdc++.h>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n, m, time = 0;
vector<int> adj[kNmax];
vector<int> idx;
vector<int> low;
vector<int> parent;
void read_input() {
int i, a, b;
ifstream f("biconex.in");
//std::cin>>n>>m;
f >> n >> m;
for (i = 1; i <= m; i++) {
f >> a >> b;
//std::cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
f.close();
}
void dfs(int i, stack<int> &stk, vector<vector<int>> &bccs) {
int childrens = 0, j, z;
time++;
idx[i] = time;
low[i] = time;
stk.push(i);
for (int u : adj[i]) {
if (!idx[u]) {
childrens++;
parent[u] = i;
dfs(u, stk, bccs);
low[i] = min(low[i], low[u]);
if (low[u] >= idx[i] && parent[i] || !parent[i]) {
vector<int> bcc;
bcc.push_back(i);
do {
z = stk.top();
stk.pop();
bcc.push_back(z);
} while (z != u);
bccs.push_back(bcc);
}
} else if (u != parent[i]) {
low[i] = min(low[i], idx[u]);
}
}
}
vector<vector<int>> get_result() {
int i;
vector<vector<int>> sol;
stack<int> stk;
idx.resize(n + 1, 0);
low.resize(n + 1);
parent.resize(n + 1, 0);
for (i = 1; i <= n; i++)
if (!idx[i])
dfs(i, stk, sol);
return sol;
}
void print_output(vector<vector<int>> result) {
int i, j;
ofstream g("biconex.out");
//std::cout<<std::endl;
//std::cout<<result.size()<<std::endl;
g << result.size() << '\n';
for (i = 0; i < result.size(); i++) {
for (j = 0; j < result[i].size(); j++)
//std::cout<<result[i][j]<<" ";
g << result[i][j] << ' ';
//std::cout<<std::endl;
g << '\n';
}
g.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}