P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

CREATE 2018/10/31 UPDATE 2018/11/01 Cat: solution Tag: 模拟 搜索

题目链接P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目和信息传递类似,不同的是这个题要求出每个点的长度。方法一样,标记+染色。

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;
int n;
int a[100010];
int col[100010];
int mark[100010];
int cir[100010];
int ans[100010];
void init(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
}
void workone(int x){
    int i=x;
    stack<int>s;
    int sz=0;
    for(i=x;col[i]==0;i=a[i]){//往后走  
        sz++;
        mark[i]=sz;
        col[i]=x;
        s.push(i);
    }
    if(col[i]!=x){//走到别的圈上了,往回走然后赋值 
        // 显然,如果和别的链相交,那么后面的路都一样,因此接着这个往回走就行。
        // s.pop();
        int qwq=0;
        while(!s.empty()){
            qwq++;
            ans[s.top()]=qwq+ans[i];
            s.pop();
        }
    }else{//走到了自己的圈上 
    //如果这条链和别的没有相交,等到链自己循环的时候,这个圈上面距离都一样是cirsz
        int cirsz=sz-mark[i]+1;
        int markqwq=1;
        for(int j=i;j!=i || markqwq;j=a[j]){//把这一个圈上的点弄了。
            //(markqwq是因为不管怎样都要有j=i。。但是不满足)
        	markqwq=0;
            ans[j]=cirsz;
            s.pop();
        }
        int qwq=0;
        while(!s.empty()){//倒着标记一条链上的。
            qwq++;
            ans[s.top()]=qwq+ans[i];
            s.pop();
        }
    }
    return ;
}
void work(){
    for(int i=1;i<=n;i++){
        if(col[i]==0){
            workone(i);
        }
    }
    for(int i=1;i<=n;i++){
        // cout<<ans[i]<<endl;
        printf("%d\n",ans[i]);
    }
}
int main(){
    init();
    work();

    return 0;
}

Search

    访客计数(AmazingCounters)

    独立IP

    AllHits

    联系以及问题反馈区


    广告

    北京华电的日子(bilibili播放)

    北京华电的日子(歌词)

    注意:视频有一些问题,比如调音等。不过由于时间等问题,暂时无法重置。。。如果有什么意见欢迎评论或者通过其他联系方式告诉我

    Table of Contents