Pagini recente » Cod sursa (job #727263) | Cod sursa (job #1361223) | Cod sursa (job #2949274) | Cod sursa (job #586726) | Cod sursa (job #3282011)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <array>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
const int MAX_N = 100000;
const int MAX_M = 200000;
int n, m;
std::vector<int> g1[MAX_N + 1];
std::vector<int> g2[MAX_N + 1];
std::vector<std::array<int, 2>> g_init[MAX_N + 1];
std::vector<std::array<int, 2>> edges;
void read() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
fin >> u >> v;
edges.push_back({u, v});
g_init[u].push_back({v, i});
g_init[v].push_back({u, i});
}
}
bool vis_edge[MAX_M + 1];
bool vis[MAX_N + 1];
void dfs_init(int node) {
vis[node] = true;
for (auto [to, idx] : g_init[node]) {
if (!vis_edge[idx]) {
g1[node].push_back(to);
g2[to].push_back(node);
vis_edge[idx] = true;
}
if (!vis[to])
dfs_init(to);
}
}
std::stack<int> stk;
void dfs1(int node) {
vis[node] = true;
for (int to : g1[node])
if (!vis[to])
dfs1(to);
stk.push(node);
}
std::vector<int> comp;
std::vector<std::vector<int>> comps;
int id[MAX_N + 1], cnt;
void dfs2(int node) {
id[node] = cnt;
vis[node] = true;
comp.push_back(node);
for (int to : g2[node])
if (!vis[to])
dfs2(to);
}
void reset_vis() {
for (int i = 1; i <= n; i++)
vis[i] = false;
}
void solve() {
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs_init(i);
reset_vis();
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs1(i);
reset_vis();
while (!stk.empty()) {
int node = stk.top();
stk.pop();
if (vis[node])
continue;
comp.clear();
cnt++;
dfs2(node);
if (comp.size() > 1)
comps.push_back(comp);
}
for (auto [x, y] : edges)
if (id[x] != id[y])
comps.push_back({x, y});
fout << comps.size() << '\n';
for (const auto & comp : comps) {
for (int x : comp)
fout << x << ' ';
fout << '\n';
}
}
int main() {
read();
solve();
return 0;
}