[CF118E] Bertown roads - Tarjan
Description
有n个交汇点和m条双向道路,一个人可以凭借现有的通道从一个点到达另一个点。确定这样一种方案,使每条道路改为单向行驶,但仍满足能够从任意一个点到达另一任意点的要求
Solution
关键是把图做成若干个环,而无解当且仅当图中有桥
因此我们先用 TARJAN 判断是否有桥,如果没有,构造解法输出,只需要一个不走重复边的 DFS 即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m;
vector<int> g[N], b[N], inv[N];
int low[N], dfn[N], ind, vis[N];
int flag_bridge;
void make(int p, int q)
{
inv[p].push_back(g[q].size());
inv[q].push_back(g[p].size());
g[p].push_back(q);
g[q].push_back(p);
b[p].push_back(0);
b[q].push_back(0);
}
void tarjan(int p, int from)
{
low[p] = dfn[p] = ++ind;
for (int i = 0; i < g[p].size(); i++)
{
int q = g[p][i];
if (q == from)
continue;
if (dfn[q] == 0)
{
tarjan(q, p);
low[p] = min(low[p], low[q]);
}
else
{
low[p] = min(low[p], dfn[q]);
}
if (low[q] > dfn[p])
flag_bridge = 1;
}
}
void print(int p)
{
vis[p] = 1;
for (int i = 0; i < g[p].size(); i++)
{
int q = g[p][i];
if (b[p][i])
continue;
b[p][i] = b[q][inv[p][i]] = 1;
if (!vis[q])
print(q);
cout << p << " " << q << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
make(u, v);
}
tarjan(1, 0);
if (flag_bridge)
{
cout << 0 << endl;
}
else
{
print(1);
}
}