题目链接：

题意:

        给出一个有n个点m条边的无向图，保证联通，现在要求将所有边给定一个方向使其变成有向图，设f(x)为点x能到达的点的个数，要求使最小的f(x)最大，并输出方案。 

思路：

        tarjan一下，答案肯定是强连通分量里点最多的一个分量，而同一个强连通里的点成环，其他分量都指向这个最大点个数的分量。

退役了，偶尔刷一下题...

1 #include 
     
        2 using namespace std;  3 const int N = 4e5 + 5;  4 struct Edge {  5     int next, to;  6 }edge[N << 1];  7 int head[N], tot;  8 int low[N], dfn[N], st[N], block[N];  9 int top, ord, scc; 10 bool instack[N]; 11 int _u[N], _v[N]; 12 int Max, pos; 13 map 
      
        mp[N]; 14 bool vis[N]; 15  16 void init() { 17     memset(head, -1, sizeof(head)); 18 } 19  20 void addedge(int u, int v) { 21     edge[tot].next = head[u]; 22     edge[tot].to = v; 23     head[u] = tot++; 24 } 25  26 void tarjan(int u, int par) { 27     low[u] = dfn[u] = ++ord; 28     st[++top] = u; 29     instack[u] = true; 30     for(int i = head[u]; ~i; i = edge[i].next) { 31         int v = edge[i].to; 32         if(v == par) 33             continue; 34         if(!dfn[v]) { 35             tarjan(v, u); 36             low[u] = min(low[u], low[v]); 37         } else if(instack[v]) { 38             low[u] = min(low[u], dfn[v]); 39         } 40     } 41     if(low[u] == dfn[u]) { 42         int v, cnt = 0; 43         ++scc; 44         do { 45             v = st[top--]; 46             instack[v] = false; 47             block[v] = scc; 48             ++cnt; 49         } while(u != v); 50         if(cnt > Max) { 51             Max = cnt, pos = v; 52         } 53     } 54 } 55  56 void dfs(int u, int p) { 57     vis[u] = true; 58     for(int i = head[u]; ~i; i = edge[i].next) { 59         int v = edge[i].to; 60         if(v == p || mp[u][v] || mp[v][u]) { 61             continue; 62         } else if(vis[v]) { 63             mp[u][v] = 1; 64             continue; 65         } 66         mp[u][v] = 1; 67         dfs(v, u); 68     } 69 } 70  71 int main() 72 { 73     init(); 74     int n, m; 75     scanf("%d %d", &n, &m); 76     for(int i = 1; i <= m; ++i) { 77         scanf("%d %d", _u + i, _v + i); 78         addedge(_u[i], _v[i]); 79         addedge(_v[i], _u[i]); 80     } 81     tarjan(1, -1); 82     dfs(pos, -1); 83     printf("%d\n", Max); 84     for(int i = 1; i <= m; ++i) { 85         if(block[_u[i]] != block[_v[i]]) { 86             if(!mp[_u[i]][_v[i]]) { 87                 printf("%d %d\n", _u[i], _v[i]); 88             } else { 89                 printf("%d %d\n", _v[i], _u[i]); 90             } 91         } else { 92             if(mp[_u[i]][_v[i]]) { 93                 printf("%d %d\n", _u[i], _v[i]); 94             } else { 95                 printf("%d %d\n", _v[i], _u[i]); 96             } 97         } 98     } 99     return 0;100 }