自动搬运

查看原文

来自洛谷，原作者为

	鲤鱼江 精神状况堪忧 | 我是？

搬运于2025-08-24 22:52:12，当前版本为作者最后更新于2024-08-07 09:08:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题被出到了模拟赛，顺手写一篇题解。

我们将 $H$ 和 $L$ 当做黑白两种颜色，两个端点颜色不同的边叫做异色边，否则叫做同色边。

不难发现一个环可以一直走下去的当且仅当：这个环上有且仅有一条同色边且同色边连接的两个点中有一个可以用作起点。

信息量可能有点大，一条一条解释。

1. 是一个环：显然，因为你肯定不能往回走。
2. 有一条同色边：因为离开一个点后会使其颜色反转，所以相当于将与该点相连的所有边的状态改变，所以如果没有同色边，最后便无法回到起点。
3. 仅有一条同色边：只有在返回起点时需要用到同色边，其他同色边走了不优。
4. 有一个作为起点：如上分析都建立在起点是同色边端点上的，若起点不是同色边端点，则说明我们走到其中一个同色边端点时就无法回溯到另一个端点（否则与这些点形成环相矛盾，直接回溯肯定会使一些点未被遍历到）。

综上便是本题用到的所有性质，我们来思考究竟怎么维护。

因为恰好一条同色边的条件很苛刻，所以可以先把异色边加入，再枚举同色边，若同色边的两个端点在异色边的生成子图上连通，则前三条性质都满足了，我们只需要对第四条性质进行判定。

不难发现问题等价与 $1$ 号节点能否在不经过环上节点的情况下到达同色边的一个端点，此时可以考虑点双。

点双的性质之一：对于任意互异三点 $x$、$y$、$z$，存在一条 $x\to z$ 的路径不经过 $y$。

所以点双的想到应是很自然的，然后以一为根遍历一下园方树，判一下子树即可，细节不多。

#include<bits/stdc++.h>

using namespace std;

namespace Fread {
	const int SIZE=1<<21;char buf[SIZE],*S,*T;
	inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
	const int SIZE=1<<21;
	char buf[SIZE],*S=buf,*T=buf+SIZE;
	inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
	inline void putchar(char c){*S++=c;if(S==T)flush();}
	struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
	struct Reader{
	    template<typename T>
    	Reader& operator >> (T& x) {
        	char c=getchar();T f=1;
        	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
        	while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
	        return *this;
    	}
	    Reader& operator >> (char& c) {c=getchar();while(c==' '||c=='\n')c=getchar();return *this;}
	    Reader(){}
	}cin;
	struct Writer{
	    template<typename T>
	    Writer& operator << (T x) {
	        if(x==0){putchar('0');return *this;}
	        if(x<0){putchar('-');x=-x;}
	        static int sta[45];int top=0;
	        while(x){sta[++top]=x%10;x/=10;}
	        while(top){putchar(sta[top]+'0');--top;}
	        return *this;
    	}
    	Writer& operator << (char c) {putchar(c);return *this;}
    	Writer& operator << (const char* str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
    	Writer(){}
	}cout;
}
#define endl '\n'
#define cin Fastio :: cin
#define cout Fastio :: cout

const int N=6e5+10;
struct edge{
	int to,ne;
	edge(int to=0,int ne=0):
		to(to),ne(ne){;}
}a[N<<1];
int h[N],cnt,n,m,bel[N],flag[N],tot,stk[N],Top,dfn[N],T,col[N];
int X[N],Y[N],f[N],root[N],low[N],idx,dep[N],id[N],IDX,siz[N];
vector < int > v[N];vector < int > p[N];char in;

/*
	1.图不一定连通，所以树也不一定连通。
	2.tot的初值
*/

void clear(){
	for(int i=1;i<=m;++i) X[i]=Y[i]=0;
	for(int i=1;i<=tot;++i){
		h[i]=bel[i]=flag[i]=stk[i]=dfn[i]=root[i]=low[i]=dep[i]=col[i]=0;
		v[i].clear();p[i].clear();
	}
	for(int i=1;i<=cnt;++i) a[i]=edge();
	cnt=tot=Top=idx=0;
}

inline void add(const int x,const int y){a[++cnt]=edge(y,h[x]);h[x]=cnt;}

void tarjan(const int x,int rt){
	dfn[x]=low[x]=++idx;stk[++Top]=x;
	if(x==rt&&v[x].empty()){--Top;p[++tot].emplace_back(x);if(!flag[x]) bel[x]=tot;return ;}
	int ct=0,tmp;
	for(int i:v[x]){
		if(!dfn[i]){
			tarjan(i,rt);
			low[x]=min(low[x],low[i]);
			if(low[i]>=dfn[x]){
				++ct;if(x!=rt||ct>1) flag[x]=1,bel[x]=0;++tot;
				if(!flag[x]) bel[x]=tot;
				p[tot].emplace_back(x);
				while(stk[Top+1]!=i){
					tmp=stk[Top--];
					p[tot].emplace_back(tmp);
					if(!flag[tmp]) bel[tmp]=tot;
				}
			}
		}else low[x]=min(low[x],dfn[i]);
	}
}

inline int In(const int x,const int y){return id[y]<=id[x]&&id[x]<=id[y]+siz[y]-1;}
void dfs(int x,int y,int rt){
	id[x]=++IDX;f[x]=y;root[x]=rt;dep[x]=dep[y]+1;siz[x]=1;
	for(int i=h[x];i;i=a[i].ne) if(a[i].to!=y) dfs(a[i].to,x,rt),siz[x]+=siz[a[i].to];
}

int main(){
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m;tot=n;int fg=0;
		for(int i=1;i<=n;++i){cin>>in;col[i]=(in=='H');}
		for(int i=1;i<=m;++i){
			cin>>X[i]>>Y[i];
			if(col[X[i]]!=col[Y[i]]){
				v[X[i]].emplace_back(Y[i]);
				v[Y[i]].emplace_back(X[i]);
			}
		}
		tarjan(1,1);
		for(int i=n+1;i<=tot;++i) for(auto j:p[i]) if(flag[j]){add(j,i);add(i,j);}
		for(int i=1;i<=n;++i) if(flag[i]) bel[i]=i;
		dfs(bel[1],0,bel[1]);
		for(int i=1;i<=m;++i){
			if(col[X[i]]!=col[Y[i]]) continue;
			if(X[i]==Y[i]) continue;
			int x=bel[X[i]],y=bel[Y[i]];
			if(root[x]!=bel[1]||root[y]!=bel[1]) continue;
    		if(flag[x]&&x!=1) x=f[x];
    		if(flag[y]&&y!=1) y=f[y];
			if((fg|=In(x,y)||In(y,x))) break;
		}
		cout<<(fg?"yes\n":"no\n");
		clear();
	}
	return 0;
}