为什么我的做法建边的时候起始点和终点一定要分两层建?不然过不了。
附代码:
#include<bits/stdc++.h>
using namespace std;
string s;
const int N=1e6+5;
vector<int> g[N];
int f1[N],f2[N];
int find(int fa[],int x){return fa[x]==x?x:fa[x]=find(fa,fa[x]);}
bool mark[N],l[N],r[N];
void add(int u,int v){
g[u].push_back(v),g[v].push_back(u);
f1[find(f1,v)]=find(f1,u);
if(s[u]!=s[v])f2[find(f2,v)]=find(f2,u);
else mark[u]=mark[v]=true;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m,q,u,v;
cin>>n>>m>>q>>s;
s=' '+s+s;
for(int i=1;i<=n*2;i++)f1[i]=f2[i]=i;
while(m--)cin>>u>>v,add(u,v+n),add(u+n,v);
for(int i=1;i<=n*2;i++){
u=find(f2,i);
for(auto v:g[i])l[u]|=(s[v]=='('&&mark[v]),r[u]|=(s[v]==')'&&mark[v]);
}
while(q--){
cin>>u>>v;
if(s[u]==')'||s[v+n]=='('||find(f1,u)!=find(f1,v+n))cout<<'0';
else if(find(f2,u)==find(f2,v+n)||l[find(f2,u)]&&r[find(f2,v+n)])cout<<'1';
else cout<<'0';
}
return 0;
}