题意：
求一个有向图中:
（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\n%d\n", _0in, max(_0in,_0out)); // ???????else printf("1\n0\n");//特判一下只有一个scc的情况， 那么只用选一个点 ???} ???return 0;}POJ 1236 Network of Schools (强连通分量缩点求度数)
原文地址：https://www.cnblogs.com/Jadon97/p/8360564.html