题意：给出一个有向图，问最少添加几条有向边使得原图强连通。
解法：求出SCC后缩点，统计一下出度为0的点和入度为0的点，二者取最大值就是答案。
还有个特殊情况就是本身就是强连通的话，答案就是0.
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int maxn = 20000 + 10;10 11 int n, m;12 13 vector G[maxn];14 15 stack S;16 int pre[maxn], low[maxn], sccno[maxn];17 int dfs_clock, scc_cnt;18 19 void dfs(int u, int fa)20 {21 low[u] = pre[u] = ++dfs_clock;22 S.push(u);23 24 for(int i = 0; i < G[u].size(); i++)25 {26 int v = G[u][i];27 if(!pre[v])28 {29 dfs(v, u);30 low[u] = min(low[u], low[v]);31 }32 else if(!sccno[v]) low[u] = min(low[u], pre[v]);33 }34 35 if(pre[u] == low[u])36 {37 scc_cnt++;38 for(;;)39 {40 int x = S.top(); S.pop();41 sccno[x] = scc_cnt;42 if(x == u) break;43 }44 }45 }46 47 void find_scc()48 {49 memset(pre, 0, sizeof(pre));50 memset(sccno, 0, sizeof(sccno));51 dfs_clock = scc_cnt = 0;52 for(int i = 1; i <= n; i++) if(!pre[i]) dfs(i, 0);53 }54 55 int in[maxn], out[maxn];56 57 int main()58 {59 int T; scanf("%d", &T);60 while(T--)61 {62 scanf("%d%d", &n, &m);63 for(int i = 1; i <= n; i++) G[i].clear();64 while(m--)65 {66 int u, v; scanf("%d%d", &u, &v);67 G[u].push_back(v);68 }69 70 find_scc();71 72 if(scc_cnt == 1) { puts("0"); continue; }73 74 memset(in, 0, sizeof(in));75 memset(out, 0, sizeof(out));76 for(int i = 1; i <= n; i++)77 for(int j = 0; j < G[i].size(); j++)78 {79 int u = sccno[i], v = sccno[G[i][j]];80 if(u != v) { out[u]++; in[v]++; }81 }82 83 int hehe = 0, haha = 0;84 for(int i = 1; i <= scc_cnt; i++)85 {86 if(!in[i]) hehe++;87 if(!out[i]) haha++;88 }89 printf("%d\n", max(hehe, haha));90 }91 92 return 0;93 }