题意:
给出一个无向图,要求转变为有向图,使所有点能到达的点数的最小值最大。
要点:
就是一个边双连通分量,不过我没学过,看了一下白书,觉得就是无向图中的强连通分量,但是其中有很多细节有点难推敲,基本思路就是:边双连通分类对应无向图,找出其中内部点数最多的边双连通分量,它的内部所有点都可以到其余点(包括自己),其余的边双连通分量可以指向最大的这个,也就是说其他所有点的能到达点数是所有的点。最后从内部点数最多的边双连通分量中任意一点开始DFS即可。但是这里有个问题,将v->u作为新边是可以的,反之u->v就是错误的,找不到原因,还是多做几道对应题目比较好。
#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 400005;
int low[maxn], pre[maxn];
int n, m, num_max, pos_max, pos;
typedef pair<int, int> ii;
vector<ii> g[maxn];
ii ans[maxn];
stack<int> st;void tarjan(int u, int fa)
{low[u] = pre[u] = ++pos;st.push(u);for (int i = 0; i < g[u].size(); i++){int v = g[u][i].first;if (v == fa)continue;if (!pre[v])tarjan(v, u);low[u] = min(low[u], low[v]);}if (low[u] == pre[u])//找到桥,此时栈中存储的点就是边双连通分量中的点{int v = 0, count = 0;while (v != u){v = st.top(); st.pop();count++;}if (count > num_max){num_max = count;pos_max = u;}}
}
void dfs(int u)
{pre[u] = 0;for (int i = 0; i < g[u].size(); i++){int v = g[u][i].first;int id = g[u][i].second;if (pre[v]){ans[id] = ii(v, u);//问题就在这里,这里如果是u->v是错误的,找不到哪里有问题dfs(v);}elseans[id] = ii(u, v);}
}int main()
{int u, v;scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++){scanf("%d%d", &u, &v);g[u].push_back(ii(v, i));g[v].push_back(ii(u, i));}tarjan(1, 0);dfs(pos_max);printf("%d\n", num_max);for (int i = 1; i <= m; i++)printf("%d %d\n", ans[i].first, ans[i].second);return 0;
}