tarjan算法可以用来求强连通分量， 强连通分量有个很好的性质就是任意2个点都是互相到达的也就是说任意2点都在一个环上. 有了这样的性质有些问题中就可以把一个强连通分量当作一个点来看待，这样就可以把它们当作一个个超级点，特别的有时候单个点也可以是一个强连通分量， 所有可以把整张图简化为DAG（有向无环图） 这样就能简化问题：
tarjan的实现 需要一个low数组记录点最小的父亲编号 dfn数组记录点的编号 stack记录子树的大小
如果点未遍历则dfn等于0遍历它，回溯时跟新low数组 如果点遍历过但是在stack中说明是该点的父亲，跟新low 如果low = dfn说明此点就是子树的父亲， 这个点之后入栈的点包括它自己都是一个强连通块，弹出这些元素。同时可以做一些操作比如计数，合并。
inline void tarjan(int x) { DFN[x] = LOW[x] = cut++; stack[++top] = x; vis[x] = 1; for(int i = h[u]; ~i; i = e[i].nes) { int v = e[i].to; if(!DFN[v]) { tarjan(v); LOW[x] = min(LOW[v], LOW[x]); } else if(vis[x]) { LOW[x] = min(LOW[x], LOW[v]); } } if(LOW[x] == DFN[x]) { //当前栈中x以及前面的元素都是一个连通块！ //可以在此缩点了 //或者做一些其他的统计工作 } }有向无环图中，如果度为0的点只有一个那么它一定能到达所有点！ 有向无环图中，如果入度为0的点只有一个那么它一定能被所有点到达！
而在tarjan缩点转化的DAG中每个点都有可能是一个强连通分量，所以就可以根据DAG的性质判断有多少满足条件的点了。
题目：
P2194 HXY烧情侣 思路：tarjan进行缩点，一个连通块只需要烧一个点就行，在缩点的时候记录下最小化花费的点，并且记录最小花费点的个数。 这样遍历所有连通块，计算出最小花费，而方案种数就是每个强连通块种最小花费点个数的乘积！
#include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<cmath> #include<string> #define ll long long #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define me(a,b) memset(a, b, sizeof(a)) #define iosos ios::sync_with_stdio(false) #define fo(a,b,c) for(int a = b; a < c; a++) using namespace std; const int maxn = 1e5 + 10; const int maxm = 3*maxn + 10; const int inf = 0x7f7f7f7f; const int mod = 1e9+7; int h[maxn], p, cost[maxn]; int n, m; int dfn[maxn], low[maxn], vis[maxn], stac[maxn], block[maxn], sum, cnt, top; struct edge { int nes, u, to; }e[maxm]; inline void add(int u, int v) { e[p].nes = h[u], e[p].to = v, e[p].u = u, h[u] = p++; } ll ans; ll type = 1; void tarjan(int x) { dfn[x] = low[x] = ++cnt; vis[x] = 1, stac[++top] = x; for(int i = h[x]; ~i; i = e[i].nes) { int v = e[i].to; if(!dfn[v]) { tarjan(v); low[x] = min(low[x], low[v]); } else if(vis[v]) { low[x] = min(low[x], low[v]); } } if(low[x] == dfn[x]) { ll t = inf; ll temp = 0; while(stac[top + 1] != x) { if(t > cost[stac[top]]) { t = cost[stac[top]]; temp = 1; } else if(t == cost[stac[top]]) temp++; vis[stac[top--]] = 0; } ans += t; type *= temp; type = type % mod; } } int main() { iosos; me(h, -1); cin>>n; fo(i, 1, n+1) cin>>cost[i]; cin>>m; fo(i,0,m) { int u, v; if(u == v) continue; cin>>u>>v; add(u, v); } fo(i, 1, n+1) if(!dfn[i]) tarjan(i); cout <<ans<<' ' <<type; return 0; }P2002 消息扩散 用到了DAG的性质，如果想从一个点出发遍历，最可能多的遍历点，那么一定要从入度为0的点出发，最好的情况就是一张DAG只有一个入度为0的点时，我们只需从这个点出发就可以到达任何点，多个入度为0的点时只需要依次从入度为0的点出发就行。 所以用tarjan将图变为DAG然后从入度为0的强连通分量出发就行。与几个超级点为0答案就是多少
#include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<cmath> #include<string> #define ll long long #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define me(a,b) memset(a, b, sizeof(a)) #define iosos ios::sync_with_stdio(false) #define fo(a,b,c) for(int a = b; a < c; a++) using namespace std; const int maxn = 1e5 + 10; const int maxm = maxn*5 + 10; const int inf = 0x7f7f7f7f; int n, m; int h[maxn], p; int dfn[maxn], low[maxn], stac[maxn], color[maxn], deg[maxn]; int cnt = 0, top = 0, sum = 0; bool vis[maxn]; struct edge { int nes, to, u; } e[maxm]; inline void add(int u, int v) { e[p].nes = h[u], e[p].u = u, e[p].to = v, h[u] = p++; } void tarjan(int x) { dfn[x] = low[x] = ++cnt; vis[x] = 1, stac[++top] = x; for(int i = h[x]; ~i; i = e[i].nes) { int v = e[i].to; if(!dfn[v]) { tarjan(v); low[x] = min(low[v], low[x]); } else if(vis[v]) { low[x] = min(low[v], low[x]); } } if(dfn[x] == low[x]) { sum++; while(stac[top + 1] != x) { color[stac[top]] = sum; //合并 vis[stac[top--]] = 0; } } } int main() { iosos; me(h, -1); me(deg, 0); cin>>n>>m; fo(i, 0, m) { int u, v; cin>>u>>v; if(u == v) continue; add(u, v); } fo(i, 1, n+1) { if(!dfn[i]) { tarjan(i); } } fo(i, 0, p) { int u = e[i].u, v = e[i].to; if(color[u] != color[v]) { deg[color[v]]++; } } int ans = 0; fo(i,1,sum+1) if(!deg[i]) ans++; cout<<ans; return 0; }P2341 [HAOI2006]受欢迎的牛 牛想被所有的6欢迎他就要被所有的6可达，所有将图缩为DAG，判断入度为0的超级点是不是只有一个，那么超级点包含的6都是最受欢迎的！如果有多个入度为0的超级点那么显然他们直接不能到达，所以没有受欢迎的6
#include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<cmath> #include<string> #define ll long long #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define me(a,b) memset(a, b, sizeof(a)) #define iosos ios::sync_with_stdio(false) #define fo(a,b,c) for(int a = b; a < c; a++) using namespace std; const int maxn = 1e5 + 10; const int maxm = maxn << 1; const int inf = 0x7f7f7f7f; int h[maxn], h1[maxn], p, p1; int dfn[maxn], low[maxn], vis[maxn], stac[maxn], top, cnt; int block[maxn], color[maxn], deg[maxn]; int n, m, sum; struct edge{ int nes, to, u; }e[maxn], e1[maxm]; inline void add(int u, int v) { e[p].nes = h[u], e[p].to = v, e[p].u = u, h[u] = p++; } inline void add1(int u, int v) { e1[p1].nes = h1[u], e1[p1].to = v,h1[u] = p1++; } void tarjan(int x) { low[x] = dfn[x] = ++cnt; vis[x] = 1, stac[++top] = x; for(int i = h[x]; ~i; i = e[i].nes) { int v = e[i].to; if(!dfn[v]) { tarjan(v); low[x] = min(low[x], low[v]); } else if(vis[v]) { low[x] = min(low[x], low[v]); } } if(low[x] == dfn[x]) { int tot = 0; ++sum; while(stac[top + 1] != x) { tot++; color[stac[top]] = sum; vis[stac[top--]] = 0; } block[sum] = tot; } } int main() { iosos; me(h, -1); me(h1, -1); cin>>n>>m; fo(i, 0, m) { int u, v; cin>>u>>v; add(u,v); } fo(i, 1, n+1) { if(!dfn[i]) tarjan(i); } fo(i,0,p) { int u = e[i].u, v = e[i].to; if(color[u] != color[v]) { add1(color[u], color[v]); deg[color[u]]++; } } int tot = 0; int tab = 0; fo(i, 1, sum+1) { if(!deg[i]) { tot++; if(tot > 1) break; tab = i; } } if(tot > 1) cout<<0; else cout<<block[tab]; return 0; }P1262 间谍网络 跟消息扩散很像，要问能不能揭发所有特务，如果能贿赂间谍的最少花费是多少，将图转化为DAG我们发现如果想揭发所有特务只能是在入度为0的超级点中都有可以行贿的特务才行，不然揭发不了全部，所以我们缩点，然后判断是不是所有入度为0的超级点都有特务，如果不是抱歉，无法揭发成功，如果是，那么每个超级点记录下最小的行贿金额就行。即可得出答案！
#include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<cmath> #include<string> #define ll long long #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define me(a,b) memset(a, b, sizeof(a)) #define iosos ios::sync_with_stdio(false) #define fo(a,b,c) for(int a = b; a < c; a++) using namespace std; const int maxn = 1e5 + 10; const int maxm = maxn << 1; const int inf = 0x7f7f7f7f; int money[maxn]; int h[maxn], h1[maxn], p, p1; int dfn[maxn], low[maxn], vis[maxn], stack[maxn], top, cnt; int color[maxn], bolck[maxn], sum; int deg[maxn]; int n, q, r; struct edge { int nes, u, to; }e[maxm], e1[maxm]; inline void add(int u, int v) { e[p].nes = h[u], e[p].to = v, e[p].u = u, h[u] = p++; } inline void add1(int u, int v) { e1[p1].nes = h1[u], e1[p1].to = v, h1[u] = p1++; } void tarjan(int x) { dfn[x] = low[x] = ++cnt; vis[x] = 1, stack[++top] = x; for(int i = h[x]; ~i; i = e[i].nes) { int v = e[i].to; if(!dfn[v]) { tarjan(v); low[x] = min(low[x], low[v]); } else if(vis[v]) { low[x] = min(low[x], low[v]); } } if(dfn[x] == low[x]) { ++sum; while(stack[top+1] != x) { color[stack[top]] = sum; bolck[sum] = min(bolck[sum], money[stack[top]]); //记录这个块里面最便宜的特务 // if(money[stack[top]] != inf) cout <<money[stack[top]] <<endl; vis[stack[top--]] = 0; } } } int main() { iosos; me(h,-1); me(h1,-1); me(money, 0x7f); me(bolck, 0x7f); //freopen("testdata (9).in", "r", stdin); cin>>n>>q; fo(i,0,q) { int id, cost; cin>>id>>cost; money[id] = cost; } cin>>r; fo(i,0,r) { int u, v; cin>>u>>v; add(u,v); } fo(i,1,n+1) if(!dfn[i] && money[i] != inf) tarjan(i), top = 0; fo(i, 1, n+1) { if(!dfn[i]) { cout<<"NO"<<endl; cout<<i<<endl; return 0; } } cout<<"YES"<<endl; fo(i, 0, p) { int u = e[i].u, v = e[i].to; if(color[u] != color[v]) { add1(color[u], color[v]); deg[color[v]]++; } } ll ans = 0; fo(i, 1, sum+1) { //cout << bolck[i] << endl; if(!deg[i]) { ans += bolck[i]; } } cout << ans; return 0; }