自动搬运

查看原文

来自洛谷，原作者为

	Acc_Robin **

搬运于2025-08-24 21:44:20，当前版本为作者最后更新于2021-05-25 14:57:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题其实没必要 tarjan ，既然已经允许 $O(n^2)$ 的复杂度，那就直接暴力给每个点判断一下是否合法即可。

1如果从一个点 $i$ 出发，经过了某个点 $j$ 的正反两个点 $j$ 和 $j+n$，那就说明 $i$ 这个情况是非法的。

我们对每个点 $i$ 和 $i+n$ 都dfs一遍，直接判断即可。

如果点 $i$ 和点 $i+n$ 都不合法，说明无解。

在代码中体现为

for(int i=1,x,y;i<=m;i++){
	x=check(i),y=check(i+m);
	if(!x&&!y)return (void)(puts("IMPOSSIBLE"));
	if(x&&y)ans[i]='?';
	if(x&&!y)ans[i]='N';
	if(!x&&y)ans[i]='Y';
}

整体代码：

#include<bits/stdc++.h>
using namespace std;
namespace Acc{
	const int N=2e3+10;
	basic_string<int>G[N];
	int n,m,d[N];
	char s[10],t[10],ans[N];
	void Dfs(int u){
		d[u]=1;
		for(auto v:G[u])if(!d[v])Dfs(v);
	}
	int check(int x){
		memset(d,0,sizeof d),Dfs(x);
		for(int i=1;i<=m;i++)if(d[i]&&d[i+m])return 0;
		return 1;
	}
	void work(){
		cin>>m>>n;
		for(int i=1,x,y,a,b;i<=n;i++)cin>>x>>s>>y>>t,a=s[0]=='Y',b=t[0]=='Y',G[x+m*(1-a)]+=y+b*m,G[y+m*(1-b)]+=x+a*m;
		for(int i=1,x,y;i<=m;i++){
			x=check(i),y=check(i+m);
			if(!x&&!y)return (void)(puts("IMPOSSIBLE"));
			if(x&&y)ans[i]='?';
			if(x&&!y)ans[i]='N';
			if(!x&&y)ans[i]='Y';
		}
		cout<<ans+1;
	}
}
int main(){
	return Acc::work(),0;
}