E - Reachability in Functional Graph

E - Reachability in Functional Graph

https://atcoder.jp/contests/abc357/tasks/abc357_e

 

思路

概念：

基环树-内生树。

https://www.cnblogs.com/Dfkuaid-210/p/14696378.html

方法：

使用拓扑排序，从入度为0的点开始，依此从外层向内层拆点，直到剩下环， 拆换过程中把拆掉的size记到目标点上size，依次累计到环点上。

最后统计环点上的所有点的size之和。

 

 

 

 

 

Code

https://atcoder.jp/contests/abc357/submissions/54442574

#include <bits/stdc++.h>
using namespace std;
#define int long long
int to[200005],deg[200005],sz[200005];
vector<int>v;
int sum=0;
void dfs(int u){deg[u]=0;v.push_back(u);sum+=sz[u];if(deg[to[u]])dfs(to[u]);
}
signed main(){int n;cin>>n;queue<int>q;for(int i=1;i<=n;i++)cin>>to[i],sz[i]=1,deg[to[i]]++;for(int i=1;i<=n;i++)if(deg[i]==0)q.push(i);while(!q.empty()){int u=q.front();q.pop();deg[to[u]]--;sz[to[u]]+=sz[u];if(deg[to[u]]==0){q.push(to[u]);}}for(int i=1;i<=n;i++){if(deg[i]){sum=0;v.clear();dfs(i);for(int a:v)sz[a]=sum;}}int ans=0;for(int i=1;i<=n;i++){ans+=sz[i];}cout<<ans;
}
/*
things to check
0.delete cerr code or use '//'
1.initallize(especially multicases)
2.int overflow/long long mle
3.if make the ans is hard , try 2-divided
4.memory &b-&a
5.function canshu position
6.the format of input
7.size enough ?
8.the name of function
9.stop copying x0->y0
*/