题意：
求一个有向图中:
（1）要选几个点才能把的点走遍
（2）要添加多少条边使得整个图强联通
分析：
对于问题1， 我们只要求出缩点后的图有多少个入度为0的scc就好， 因为有入度的scc可以从其他地方到达。
对于问题2， 每个入度为0的scc， 都可以补一条边可以变成强连通图， 每个出度为0的scc， 也可以补一条边使其变成强连通图。 所以答案就是max（入度为0scc个数，出度为0scc个数）。
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<string> #include<sstream> #include<map> #include<stack> #include<vector> #include<algorithm> #include<cmath> #define mem(a) memset(a, 0, sizeof(a)) #define rep(i,a,b) for(int i = a; i < b; i++) #define _rep(i,a,b) for(int i = a; i <= b; i++) using namespace std; const int maxn = 107; vector<int> G[maxn]; int n, m, Index = 1, scc_cnt = 0; int dfn[maxn], low[maxn], vis[maxn], scc[maxn]; int in_deg[maxn], out_deg[maxn]; stack<int> s; void tarjan(int u){ dfn[u] = Index; low[u] = dfn[u]; Index++; vis[u] = 1; s.push(u); for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; if(!dfn[v]){ tarjan(v); low[u] = min(low[v], low[u]); }else if(vis[v]){ low[u] = min(low[u], dfn[v]); } } if(dfn[u] == low[u]){ vis[u] = 0; scc[u] = scc_cnt; int t; for(;;){ int t = s.top(); s.pop(); scc[t] = scc_cnt; vis[t] = 0; if(t == u) break; } scc_cnt++; } } int main(){ while(~scanf("%d", &n)){ _rep(i,1,n) G[i].clear(); mem(dfn), mem(low), mem(vis), mem(scc), mem(in_deg), mem(out_deg); Index = 1, scc_cnt = 0; _rep(i,1,n){ int v; while(scanf("%d", &v) && v){ G[i].push_back(v); m++; } } _rep(i,1,n){ if(!dfn[i]) tarjan(i); } _rep(u,1,n) rep(i,0,G[u].size()){//缩点，枚举每条边， 如果不在同一个scc说明这是新图中的一条边 int v = G[u][i]; if(scc[u] != scc[v]){ out_deg[scc[u]]++, in_deg[scc[v]]++; } } int _0in = 0, _0out = 0; //入度为0的scc ， 出度为0的scc rep(i,0,scc_cnt){ if(in_deg[i] == 0) _0in++; if(out_deg[i] == 0) _0out++; } if(scc_cnt > 1) printf("%d %d ", _0in, max(_0in,_0out)); // else printf("1 0 ");//特判一下只有一个scc的情况， 那么只用选一个点 } return 0; }