https://www.luogu.org/problemnew/show/P2921
C++版本一
朴素
一、为了实现这一方法，我们对每个点设置两个属性：
1、颜色 (color)(color) ： 此节点第一次被访问时，这条访问他的路径是由那个节点发出的（起点）。
2、时间戳 (dfn)(dfn) ：此节点第一次被访问时，他到发出这条路径的起点的距离（发出节点的 dfn = 0dfn=0，第二个被访问的节点的 dfn = 1dfn=1，第三个 dfn = 2dfn=2 ......）
有了这两个属性，我们就可以计算环的大小，方法如下：
1、从某一节点发出路径
2、走到某个节点上（包括起点），如果这个节点没有被染色，那么染成自己的颜色，并标记上 dfndfn
3、走到某个节点上，如果这个节点已经被染成了自己的颜色，那么环的大小就出来了：当前时间 (cnt)(cnt) -− 此节点 dfndfn
到了这一步，实际上已经解决了另一个更简单的问题：NOIP2015 信息传递。 接下来就是本题特色了
二、对于每一只奶牛（或者说每一个起点、颜色、路径），我们记录如下两个属性：
1、环的大小 (minc)(minc) ：每条路径最终都会进入环中，或者起点本身就在环中，我们记录下这个环的大小为之后服务
2、入环时间戳 (sucdfn)(sucdfn) ：这条路径什么时候会进入环中，同样是为之后服务的一个属性
首先讲解一下如果得到这两个属性：
1、在上一节中我们已经讲了如何初步获取环的大小，入环时间戳只要记录为那个交点的时间戳即可
2、如果走到了之前走过的节点，那么新的路径必然进入之前路径的环中，直接把这个环的大小要过来就行了。入环时间戳则分两种情况：
i. 如果这个节点不在环中，“原路径的入环时间戳 -− 原路径中此节点的时间戳 + 新路径当前时间” 即为新路径的入环时间戳;
ii. 而如果这个节点在环中，直接就是新路径当前时间。
iii. 判断方法则是 “原路径的入环时间戳 -− 原路径中此节点的时间戳” 是否大于 00，综合起来就是：“max(max(原路径的入环时间戳 -− 原路径中此节点的时间戳, \;0),0) + 新路径当前时间”
三、把上面的问题都解决了，出答案就太简单了：
1、第一节中的发现环的大小之后，答案就是“当前时间”
2、第二节中与之间走过的节点相遇并记录完信息后，答案是 “入环时间戳 + 环的大小”
至此本题已经完美解决，且没有用到任何算法。贴代码：
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,sum;
int a[N];
int dist[N];
int color[N];
int dfn[N];
int sucdfn[N];
char str;
int minc[N];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int cow = 1; cow <= n; ++cow)
{
for(int i = cow, cnt = 0; ; i = a[i], ++cnt)
{
if(!color[i]) {
color[i] = cow;
dfn[i] = cnt;
}
else if(color[i] == cow) {
minc[cow] = cnt - dfn[i];
sucdfn[cow] = dfn[i];
cout << cnt << endl;
break;
}
else {
minc[cow] = minc[color[i]];
sucdfn[cow] = cnt + max(sucdfn[color[i]] - dfn[i], 0);
cout << sucdfn[cow] + minc[cow] << endl;
break;
}
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
强连通分量SCC
参考文章：https://blog.csdn.net/weixin_43272781/article/details/88557457
#include<bits/stdc++.h>
using namespace std;
const int Maxn=100005;
int next[Maxn];
int ans[Maxn];
int head[Maxn],cnt;
struct road
{
int to,next;
}e[Maxn*2];
void add(int a,int b)
{
cnt++;
e[cnt].to=b;
e[cnt].next=head[a];
head[a]=cnt;
}
int sum,color[Maxn],low[Maxn],ins[Maxn],tim[Maxn],sta[Maxn],top=1,col;
int Lemon[Maxn];
void Tarjan(int x)
{
sum++;
tim[x]=low[x]=sum;
sta[top]=x;
top++;
ins[x]=1;
for(int i=head[x];i!=0;i=e[i].next)
{
if(ins[e[i].to]==0)
{
Tarjan(e[i].to);
low[x]=min(low[x],low[e[i].to]);
}
else if(ins[e[i].to]==1)
low[x]=min(low[x],tim[e[i].to]);
}
if(tim[x]==low[x])
{
col++;
do
{
top--;
color[sta[top]]=col;
ins[sta[top]]=-1;
}while(sta[top]!=x);
}
return ;
}
void search(int root,int x,int step)
{
if(ans[x]!=0) {
ans[root]=ans[x]+step;
return ;
}
else search(root,next[x],step+1);
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&next[i]);
add(i,next[i]);
if(next[i]==i) ans[i]=1;//注意特判环为1的情况。
}
for(int i=1;i<=n;i++)
if(ins[i]==0) Tarjan(i);
for(int i=1;i<=n;i++)
Lemon[color[i]]++;//记录环的大小
for(int i=1;i<=n;i++)
if(Lemon[color[i]]!=1) ans[i]=Lemon[color[i]];//处理在环内的点
for(int i=1;i<=n;i++)
if(ans[i]==0) search(i,next[i],1);//处理在环外的点。
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
} C++版本三
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,to[N],rd[N],w[N],dep[N],mk[N];char vis[N],ins[N];
int dfs(int x){
int t=to[x];vis[x]=ins[x]=1;
if(!vis[t]){dep[t]=dep[x]+1;w[x]=dfs(t);w[x]+=(mk[t]?(mk[x]=(mk[x]!=2?1:0),0):1);}
else if(ins[t])w[x]=dep[x]-dep[t]+1,mk[x]=1,mk[t]=(x==t?0:2);
else w[x]=w[t]+1;
ins[x]=0;return w[x];
}
int main(){
ios::sync_with_stdio(false);cin>>n;int x;
for(int i=1;i<=n;++i)cin>>to[i],++rd[to[i]];
for(int i=1;i<=n;++i)if(!rd[i])w[i]=1,dfs(i);
for(int i=1;i<=n;++i)if(!vis[i])dfs(i);//totally a cycle
for(int i=1;i<=n;++i)cout<<w[i]<<endl;
return 0;
} C++版本四
题解：
拓扑排序删链 → 对环上的点计算答案 → dfs计算其他点的答案。
环上的点答案都一样，可以一遍dfs跑出来；
其他点的答案在dfs返回的时候+1即可。
#include <cstdio>
#define maxn 100010
int next[maxn], in[maxn], ans[maxn];
bool vis[maxn];
void del(int cur) {
vis[cur] = true;
in[next[cur]]--;
if(!in[next[cur]]) del(next[cur]);
}
int calccircle(int cur, int depth) {
ans[cur] = depth;
if(ans[next[cur]]) return depth;
else return ans[cur] = calccircle(next[cur], depth + 1);
}
int calc(int cur) {
if(ans[cur]) return ans[cur];
else return ans[cur] = calc(next[cur]) + 1;
}
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", next + i), in[next[i]]++;
for(int i = 1; i <= n; i++) if(!in[i] && !vis[i]) del(i);
for(int i = 1; i <= n; i++) if(in[i] && !ans[i]) calccircle(i, 1);
for(int i = 1; i <= n; i++) if(!in[i] && !ans[i]) calc(i);
for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}
京公网安备 11010502036488号