图论 连通性 CF1428B
Prean
2020-10-18 09:14:49
打比赛的时候sb了，用了一个似乎原本可以不用的东西来找环。。。
首先，根据题意，我们可以连成一张图，而蛇能不能回到自己的家， 只需要在一个环上就行了。
问题是怎么找环，我用了 Tarjan。。。
具体做法是每个强连通的大小如果不为 $ 1 $，就把这个强连通的大小计入答案。
还有就是记得清空。
code:
```cpp
#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);
}
}
```