给定一个有向图，求：
1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点。
2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点。
先处理环的问题，tarjan 缩点
对于第一个问题就是求DAG上入度为0的点个数。
对于第一个问题就是求DAG上max(入度为0的点数,出度为0的点数，入出点相连）；
注：n=1时单独考虑
#include<cstdio> #include<algorithm> #include<cstring> #include<map> #include<string> #include<stack> using namespace std; stack <int> state; map <string,int> id; const int N = 10010; struct Edge{ int to, next, from, del; }ed[N*2]; int head[N], place[N], vis[N], exi[N], nodel[N]; int dfn[N], low[N]; int duin[N], duout[N]; int idc, cnt, idx, tot, ans, n; void adde(int u,int v){ ed[++idc].to = v; ed[idc].from = u; ed[idc].next = head[u]; head[u] = idc; } void tarjan(int u){ dfn[u] = low[u] = ++idx; vis[u] = exi[u] = 1; state.push(u); for(int k=head[u]; k; k=ed[k].next){ int v = ed[k].to; if( !vis[v] ){ tarjan( v ); low[u] = min(low[u], low[v]); } else if( exi[v] ){ low[u] = min(low[u], dfn[v]); } } if(dfn[u] == low[u]){ int t = -1; while(t != u){ t = state.top(); place[t] = u;//强连通分量缩点到u exi[t] = 0; state.pop(); } place[u] = u; } } void cut(){ for(int i=1; i<=idc; i++){ int u = ed[i].from, v = ed[i].to; if(place[u] == u && place[v] == v) { duin[v]++; duout[u]++; //统计入度出度 continue; } if(place[u] != place[v]) adde(place[u], place[v]); ed[i].del = 1;//删边 if(place[u] != u) nodel[u] = 1;//删点 if(place[v] != v) nodel[v] = 1; } } void dfs(int u){ for(int k=head[u]; k; k=ed[k].next){ int v = ed[k].to; if( ed[k].del ) continue; if( !vis[v] ){ dfs(v); vis[v] = 1; } } } void work1(){ for(int i=1; i<=n; i++){ if( !duin[i] && !nodel[i] ) tot++; } } void work2(){ int ans1 = 0, ans2 = 0, mm = 0; for(int i=1; i<=n; i++){ if( nodel[i] ) continue; if( !duin[i] ) ans1++; if( !duout[i] ) ans2++; mm++; } ans = max(ans1, ans2); if( mm == 1 ) ans = 0;//只有一个点的情况 } int main(){ //freopen("break.in", "r", stdin); //freopen("break.out", "w", stdout); scanf("%d", &n); int cc; for(int i=1; i<=n; i++){ scanf("%d", &cc); while( cc ){ adde(i, cc); scanf("%d", &cc); } } for(int i=1; i<=n; i++) if(!vis[i]) tarjan(i); cut(); work1(); work2(); printf("%d\n%d", tot, ans); return 0; }