Kosaraju算法 O(n+m)
vector s;void dfs1(int u) { vis[u] = true; for (int v : g[u]) if (!vis[v]) dfs1(v); s.push_back(u);}void dfs2(int u) { color[u] = sccCnt; for (int v : g2[u]) if (!color[v]) dfs2(v);}void Kosaraju() { s.clear(); for (int i = 1; i <= n; ++i) if (!vis[i]) dfs1(i); sccCnt = 0; for (int i = n; i >= 1; --i) if (!color[s[i]]) { ++sccCnt; dfs2(s[i]) }} 首先考虑假如一个间谍没办法被揭发不能被贿赂，也就是他不是可行的入口点也没有别人指向他，那么无解。 否则可能要若干个入度为0的点，这些点必须被贿赂，且这些点能到达的点不需要再贿赂。 否则一定存在环，或者多个环交在一起的，而这些环都是同一强连通分量内的，找这个强连通分量里面的最小的那个。 有个问题就是加入强连通分量里的都不能被贿赂就很尴尬了，所以干脆一开始就把强连通分量用编号最小的点来代替？
这个就是在dfs1的时候把额外的信息维护好了，然后在dfs2的时候维护这个强连通分量的最小花费以及假如是INF的话的最小id。
#includeusing namespace std;typedef long long ll;const int MAXN = 3005;const int INF = 0x3f3f3f3f;int n,w[MAXN], indeg[MAXN];vector G[MAXN], G2[MAXN];//从i点出发的连通分量，染色为c1[i]int c1[MAXN],cntc1;bool visc1[MAXN];//i点所在的强连通分量，染色为c2[i]int c2[MAXN],cntc2;int minCost[MAXN], minID[MAXN];int s[MAXN],cnts;void dfs1(int u,int c) { c1[u]=c; for (int v : G[u]) if (!c1[v]) dfs1(v,c); s[++cnts]=u;}void dfs2(int u, int &minid) { c2[u] = cntc2; minCost[cntc2] = min(minCost[cntc2], w[u]); minid = min(minid, minID[cntc2]); for (int v : G2[u]) if (!c2[v]) dfs2(v, minid);}void Kosaraju(ll &sum, int &minid) { minid = INF; for (int i = 1; i <= n; ++i) if (!c1[i]){ ++cntc1; dfs1(i,cntc1); } for (int i = n; i >= 1; --i) { if (!c2[s[i]]) { ++cntc2; minCost[cntc2] = INF; minID[cntc2] = INF; dfs2(s[i], minid); } if(minCost[cntc2] == INF) minid = min(minid, minID[cntc2]); else{ if(!visc1[c1[s[i]]]){ visc1[c1[s[i]]]=true; sum += minCost[cntc2]; } } }}int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku int p; scanf("%d%d", &n, &p); memset(w, INF, sizeof(w[0]) * (n + 1)); for(int i = 1; i <= p; ++i) { int id, c; scanf("%d%d", &id, &c); w[id] = c; } int m; scanf("%d", &m); for(int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); ++indeg[v]; G[u].emplace_back(v); G2[v].emplace_back(u); } ll sum = 0; for(int i = 1; i <= n; ++i) { if(indeg[i] == 0 && w[i] == INF) { puts("NO"); printf("%d\n", i); return 0; } else if(indeg[i] == 0) { //处理了所有入度为0的点，剩下的必定是独立环 ++cntc1; dfs1(i,cntc1); visc1[cntc1]=true; sum += w[i]; } } int minid; Kosaraju(sum, minid); if(minid == INF) { puts("YES"); printf("%lld\n", sum); } else { //某个强连通分量里有不能被贿赂的点 puts("NO"); printf("%d\n", minid); } return 0;}
首先每个入链必须都要给一套，然后剩下的必有环，或者环带出链。这样就很麻烦了。把整个图的强连通分量缩成点之后，变成若干独立的链（这些链可能会交叉）。入度为0的点就是子问题1的答案。子问题2里面，考虑每次多连一条边可以消除至多1个入度为0的和1个出度为0的（就算是孤立点，也是要连一条入边一条出边才能强连通），整个图强连通肯定存在一种首尾相连的办法。答案为两者间的最大值。特例是缩点之后假如只剩下一个点，那么不需要连边。
注意一定要先处理掉链，然后进去找强连通分量，成功缩点之后新图的G的边记得要去重，方便的话可以用set，怕卡就vector然后sortunique。
#includeusing namespace std;typedef long long ll;const int MAXN = 105;const int INF = 0x3f3f3f3f;int n, w[MAXN], indeg[MAXN];vector G[MAXN], G2[MAXN];//从i点出发的连通分量，染色为c1[i]int c1[MAXN], cntc1;//i点所在的强连通分量，染色为c2[i]int c2[MAXN], cntc2;//第i个强连通分量内的点vector C2[MAXN];int s[MAXN], cnts;void dfs1(int u) { c1[u] = cntc1; for (int v : G[u]) if (!c1[v]) dfs1(v); s[++cnts] = u;}void dfs2(int u) { C2[cntc2].push_back(u); c2[u] = cntc2; for (int v : G2[u]) if (!c2[v]) dfs2(v);}void Kosaraju() { //再计算环 for (int i = 1; i <= n; ++i) if (!c1[i]) { ++cntc1; dfs1(i); } for (int i = n; i >= 1; --i) if (!c2[s[i]]) { ++cntc2; dfs2(s[i]); }}set G3[MAXN];int indeg3[MAXN], outdeg3[MAXN];int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku scanf("%d", &n); for(int u = 1; u <= n; ++u) { int v; while(1) { scanf("%d", &v); if(!v) break; G[u].push_back(v); G2[v].push_back(u); ++indeg[v]; } } for (int i = 1; i <= n; ++i) if (!c1[i] && indeg[i] == 0) { ++cntc1; dfs1(i); } Kosaraju(); if(cntc2 == 1) { //只有一个强连通分量 printf("%d\n%d\n", 1, 0); } else { for(int u = 1; u <= cntc2; ++u) { for(auto ui : C2[u]) { for(auto vi : G[ui]) { if(c2[vi] != u) { G3[u].insert(c2[vi]); ++indeg3[c2[vi]]; ++outdeg3[u]; } } } } /*for(int i = 1; i <= n; ++i) { printf("%d:%d\n", i, c2[i]); } puts(""); for(int i=1;i<=cntc2;++i){ printf("u=%d\n",i); for(auto v:G3[i]) printf(" v=%d\n",v); }*/ int in0 = 0, out0 = 0; for(int u = 1; u <= cntc2; ++u) { if(indeg3[u] == 0) ++in0; if(outdeg3[u] == 0) ++out0; } printf("%d\n%d\n", in0, max(in0, out0)); } return 0;}