关于本题做法的疑问
查看原帖
关于本题做法的疑问
653000
bigclever楼主2024/8/2 14:22

为什么我的做法建边的时候起始点和终点一定要分两层建?不然过不了。

附代码:

#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;
}
2024/8/2 14:22
加载中...