蒟蒻的小窝

蒟蒻的小窝

题解 P6706 【[COCI2010-2011#7] KUGLICE】

posted on 2020-09-19 19:30:49 | under 题解 |

首先第一个需要倒看,因为删边不好解决。再一个就是传球, 其实对于一个节点而言,就 $3$ 种情况,

$1$:叶节点。

$2$:在某条线路中。

$3$:在圈上。

对于 $1$ 和 $2$ 并查集没问题,我们可以通过并查集来实现的,就是让后者当祖先,这样就可以把球接住。对于 $3$ 我们把它引导到一个虚拟点上就OK了。

Code:

#include<bits/stdc++.h>
#define maxn 300005
using namespace std;
int top,n,Q,fa[maxn],son[maxn],ans[maxn];
bool vis[maxn];
struct ZS{
    int flg,x;
}A[maxn];
int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return ret*f;
}
int Get(int x){return fa[x]==x?x:fa[x]=Get(fa[x]);}
void merge(int x,int y){
    int fx=Get(x),fy=Get(y);
    if (fx==fy) fa[fx]=fa[fy]=n+1;else fa[fx]=fy;
}
int main(){
    n=read();
    for (int i=1;i<=n;i++){
        son[i]=read();
        if(!son[i]) vis[i]=1;//真正的祖先,即最后接球那家伙,他没儿子节点所以不需要单独给他建图 
        fa[i]=i;
    }
    fa[n+1]=n+1;//虚拟的点,等下把有圈的都往这个虚拟点引导 
    Q=read();
    for (int i=1;i<=Q;i++){
        int flg=read(),x=read();
        if(flg==2) vis[x]=1;//等下倒建图用 
        A[i]=(ZS){flg,x};
    }
    for (int i=1;i<=n;i++)//先把没被干掉的边所构建的图搞出来 
      if (!vis[i]) merge(i,son[i]);
    for (int i=Q;i>=1;i--)
      if(A[i].flg==2) merge(A[i].x,son[A[i].x]);
      else ans[++top]=Get(A[i].x);
    for (int i=top;i>=1;i--) ans[i]!=n+1?printf("%d\n",ans[i]):printf("CIKLUS\n");
    return 0;
}