题意

给定一个有向图，问至少增加多少条边才能使得整个图变成一个强连通分量。

思路

这道题是个结论题。缩点后，统计每个点的入度和出度。入度为0的点的数量以和出度为0的点的数量取最大值，这就是最终的结果。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>using namespace std;const int N = 110, M = 10010;int n;
int h[N], e[M], ne[M], idx;
int low[N], dfn[N], timestamp;
stack<int> stk;
bool in_stk[N];
int id[N], sz[N], scc_cnt;
int din[N], dout[N];void add(int a,int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void tarjan(int u)
{low[u] = dfn[u] = ++ timestamp;stk.push(u), in_stk[u] = true;for(int i=h[u];~i;i=ne[i]){int j = e[i];if(!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if(in_stk[j]) low[u] = min(low[u], dfn[j]);}if(dfn[u]==low[u]){int v;scc_cnt ++;do{v = stk.top();stk.pop();in_stk[v] = false;id[v] = scc_cnt;sz[scc_cnt] ++;}while(v!=u);}
}int main()
{cin >> n;memset(h,-1,sizeof(h));for(int i=1;i<=n;i++){int t;while(cin>>t,t) add(i,t);}for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=n;i++){for(int j=h[i];~j;j=ne[j]){int k = e[j];int a = id[i], b = id[k];if(a!=b){dout[a] ++;din[b] ++;}}}int sa = 0, sb = 0;for(int i=1;i<=scc_cnt;i++){if(!din[i]) sa ++;if(!dout[i]) sb ++;}cout << sa << endl;if(scc_cnt==1) cout << 0 << endl;else cout << max(sa,sb) << endl;return 0;
}