[USACO08DEC]Trick or Treat on the Farm

一颗基环树,则先处理环,再 DFS 处理其他结点即可

不知为何是蓝题

#include<cstdio>
#include<queue>
using namespace std;
const int N=100005;
int n,nex[N],id[N],ans[N];
bool vis[N];
queue<int> q;
void dfs(int u){// 处理剩下的树边
    if(vis[u])return;
    dfs(nex[u]);
    vis[u]=1,ans[u]=ans[nex[u]]+1;
}
int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&nex[i]),id[nex[i]]++;
    for(int i=1;i<=n;i++)if(id[i]==0)q.push(i);
    while(!q.empty()){int k=q.front();q.pop();
        id[nex[k]]--;
        if(id[nex[k]]==0)q.push(nex[k]);
    }// 筛环
    for(int i=1;i<=n;i++)if(id[i]){// 处理每个环
        int len=1;
        for(int j=nex[i];j!=i;j=nex[j])len++;
        vis[i]=1,ans[i]=len,id[i]=0;
        for(int j=nex[i];j!=i;j=nex[j])vis[j]=1,ans[j]=len,id[j]=0;
    }
    for(int i=1;i<=n;i++)dfs(i);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

 上一篇
[ZJOI2007] 棋盘制作 [ZJOI2007] 棋盘制作
悬线法。以每一个点向上达到的最长的长度作为悬线,左右扫,记录可以到达的最左边的长度以及最右边的长度,再以此更新答案即可。 更具体的, 表示从 往上最长的黑白相间的格子的高度; 表示从
2018.11.17
下一篇 
欧拉函数 | 欧拉定理 欧拉函数 | 欧拉定理
摘要 复习一下欧拉定理,顺便打了洛谷新出炉的模板~ 欧拉函数定义欧拉函数用希腊字母 表示, 表示 的欧拉函数。 的值为小于等于 且与 互质的数的
2018.11.16
  目录