[COCI Contest #7 pE][Disjoint Set] KUGLICE

可以在這邊的Contest 7中找到題目說明和測資

並查集專題中的題目......
思路也不是很困難，基本上跟這篇的思路完全一樣，可以直接參考。

說說本題的細節部份。可能是我經驗太少，沒做過非得用迭代去dfs的題目.....因為第10筆測資會讓遞迴高達3x10^5層。怎麼實做迭代困擾了我頗久。

剩下的就是基本的時光倒流方法，還有並查集的查找函數不要粗心寫錯就行了。

#include<stack>
#include<cassert>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn=300000+5;
const int maxQ=300000+5;
int out[maxn],init[maxn],fin[maxn];
int findset(int x) {return fin[x]==-1 || x==fin[x]?x:fin[x]=findset(fin[x]);}
struct Query
{
    int type,x;
}qu[maxQ];
stack<int> S;
void dfs(int now)
{
    S.push(now);
    int ret=2147483647;
    while(!S.empty())
    {
        now=S.top();
        fin[now]=-1;
        if(ret!=2147483647) {fin[now]=ret;S.pop();continue;}
        if(out[now]==-1) ret = (fin[now]=now);
        else if(fin[out[now]]==-1) ret=-1;
        else S.push(out[now]);
    }
}
int main()
{
    freopen("kuglice.in.10","r",stdin);
    freopen("out","w",stdout);
    int n,Q;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",init+i);if(init[i]==0) init[i]=-1;out[i]=init[i];}
    scanf("%d",&Q);
    for(int i=0;i<Q;i++)
    {
        scanf("%d%d",&qu[i].type,&qu[i].x);
        if(qu[i].type==2) out[qu[i].x]=-1;
    }
    for(int i=1;i<=n;i++) if(!fin[i]) dfs(i);
    vector<int> vec;
    for(int i=Q-1;i>=0;i--)
    {
        if(qu[i].type==1) vec.push_back(fin[findset(qu[i].x)]);
        else if(fin[findset(qu[i].x)]==fin[findset(init[qu[i].x])]) fin[findset(qu[i].x)]=-1;
        else fin[findset(qu[i].x)]=fin[init[findset(qu[i].x)]];
    }
    for(int i=vec.size()-1;i>=0;i--)
        if(vec[i]==-1) printf("CIKLUS\n"); else printf("%d\n",vec[i]);
}