P3007 The Continental Cowngress G 题解
Acc_Robin
·
·
题解
这道题其实没必要 tarjan ，既然已经允许 O(n^2) 的复杂度，那就直接暴力给每个点判断一下是否合法即可。
1如果从一个点 i 出发，经过了某个点 j 的正反两个点
我们对每个点 $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';
}
```
整体代码：
```cpp
#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;
}
```