CF1428B题解

打比赛的时候sb了，用了一个似乎原本可以不用的东西来找环。。。

首先，根据题意，我们可以连成一张图，而蛇能不能回到自己的家，只需要在一个环上就行了。

问题是怎么找环，我用了 Tarjan。。。

具体做法是每个强连通的大小如果不为 \(1\)，就把这个强连通的大小计入答案。

还有就是记得清空。

code:

#include<cstdio>

const int M=3e5+5;

struct Edge{

    int to;Edge*nx;

}e[M<<1],*h[M],*cnt=e;

int n,ans,dfc,top,is[M],stk[M],low[M],dfn[M];

inline void Add(const int&u,const int&v){

    *cnt=(Edge){v,h[u]};h[u]=cnt++;

}

inline int min(const int&a,const int&b){

    return a>b?b:a;

}

void Tarjan(int u){

    is[stk[++top]=u]=true;

    low[u]=dfn[u]=++dfc;

    for(Edge*E=h[u];E;E=E->nx){

        int v=E->to;

        if(!dfn[v]){

            Tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(is[v])low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

        int v,siz=0;

        do is[v=stk[top--]]=0,++siz; while(v!=u);

        if(siz>1)ans+=siz;

    }

}

signed main(){

    int T,i;char s;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);getchar();

        for(i=1;i<=n;++i){

            h[i]=NULL;

            low[i]=dfn[i]=0;

        }

        top=dfc=ans=0;

        for(i=1;i<=n;++i){

            s=getchar();

            if(s=='<')Add(i%n+1,i);

            else if(s=='>')Add(i,i%n+1);

            else Add(i,i%n+1),Add(i%n+1,i);

        }

        getchar();

        for(i=1;i<=n;++i)if(!dfn[i])Tarjan(i);

        printf("%d\n",ans);

    }

}

巴特西

CF1428B题解

最新文章

热门文章