Description
X先生来到了一个奇怪的国家旅行。这个国家有N个城市，每个城市均有且仅有一个机场，但是这机场所有航班只飞往一个城市。每个城市有一个游览价值，第i个城市的游览价值为A[i]。
现在他想知道，从第i个城市出发，并只坐飞机飞往下一个城市，游览价值之和最多是多少（一个城市游览多次只计算1次游览价值）
Input
输入文件travel.in的第1行为一个正整数N。
第2行有N个非负整数A[i]，表示了每个城市的游览价值。
第3行有N个正整数F[i]，表示第i个城市的航班飞往的城市为F[i]，可能出现F[i]=i的情况。
Output
输出文件travel.out包括N行，第i行包含一个非负整数，表示从第i个城市出发游览价值之和的最大值为多少。
Sample Input
8
5 4 3 2 1 1 1 1
2 3 1 1 2 7 6 8
Sample Output
12
12
12
14
13
2
2
1
思路
- tarjan缩点然后拓扑序，完了
- 看起来没有c++代码的题解，来发一篇
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn=200003;
queue<int> q;
vector<int> e[maxn];
int n,nxt[maxn],val[maxn],cnt,num,w[maxn],r[maxn];
int dfn[maxn],low[maxn],top,vis[maxn],s[maxn],bel[maxn];
void tarjan(int x){
dfn[x]=low[x]=++cnt,vis[x]=1,s[++top]=x;
int v=nxt[x];
if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
else if(vis[v]) low[x]=min(low[x],dfn[v]);
if(dfn[x]==low[x]){
++num;
do{vis[s[top]]=0,w[num]+=val[s[top]],bel[s[top--]]=num;}while(x!=s[top+1]);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
for(int i=1;i<=n;++i) scanf("%d",&nxt[i]);
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;++i) if(bel[i]!=bel[nxt[i]]) ++r[bel[i]],e[bel[nxt[i]]].push_back(bel[i]);
for(int i=1;i<=num;++i) if(!r[i]) q.push(i);
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=0;i<e[x].size();++i){
if(!--r[e[x][i]]) q.push(e[x][i]);
w[e[x][i]]+=w[x];
}
}
for(int i=1;i<=n;++i) cout<<w[bel[i]]<<'
';
return 0;
}