题目大意
给出一个无向连通图,让你改造成一个有向图,并保证强连通。
解题思路
先思考,将无向图改成有向图,需要顾及到一些割边,因为把割边删掉后,原图就不联通了,所以改造后的有向图需要完整的保留割边。
而对于不是割边的边,我们只需要保留一条边,可以在 tarjan
时,记录下来。
需要注意的:多测不清空,亲人两行泪。
AC CODE
#include<bits/stdc++.h>
using namespace std;
struct Fastio
{
template <typename T>
inline Fastio operator>>(T &x)
{
x = 0;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return *this;
}
inline Fastio &operator<<(const char *str)
{
int cur = 0;
while (str[cur])
putchar(str[cur++]);
return *this;
}
template <typename T>
inline Fastio &operator<<(T x)
{
if (x == 0)
{
putchar('0');
return *this;
}
if (x < 0)
putchar('-'), x = -x;
static int sta[45];
int top = 0;
while (x)
sta[++top] = x % 10, x /= 10;
while (top)
putchar(sta[top] + '0'), --top;
return *this;
}
} io;
#define _ 20005
int n, m, opt;
int tot = 1, head[_], from[_ << 1], to[_ << 1], nxt[_ << 1];
int dol[_];
int cnt_node, cntn, low[_], dfn[_], id[_], vis[_ << 1];
stack<int> s;
int u[_], v[_];
int js(int x)
{
return (x % 2) ? x + 1 : x - 1;
}
void add(int u, int v)
{
from[++tot] = u;
to[tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void tarjan(int u, int fa)
{
low[u] = dfn[u] = ++cnt_node;
s.push(u);
for(int i = head[u]; i; i = nxt[i])
if(vis[i] == -1)
{
if(to[i] == fa) continue;
vis[i] = 1;
vis[i ^ 1] = 0;
if(!dfn[to[i]])
{
tarjan(to[i], u);
low[u] = min(low[u], low[to[i]]);
if(low[to[i]] > dfn[u]) vis[i ^ 1] = 1;
}
else low[u] = min(low[u], dfn[to[i]]);
}
}
void init()
{
tot = 1;
cntn = 0;
cnt_node = 0;
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(id, 0, sizeof id);
while(!s.empty()) s.pop();
memset(u, 0, sizeof u);
memset(v, 0, sizeof v);
memset(head, 0, sizeof head);
memset(vis, -1, sizeof vis);
}
signed main()
{
while(1)
{
io >> n >> m;
if(!n && !m) break;
init();
for(int i = 1; i <= m; ++i)
{
io >> u[i] >> v[i];
add(u[i], v[i]);
add(v[i], u[i]);
}
io << ++opt << "\n" << "\n";
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i, 0);
for(int i = 2; i <= tot; ++i)
{
if(vis[i])
{
io << from[i] << " " << to[i] << "\n";
}
}
io << "#" << "\n";
}
return 0;
}