【2023上海大学春季赛】J. Juxtaposed brackets | 栈

标题链接

Problem – J – Codeforces

标题

递归界说集合 $B$ 如下：

(1)$()\in B$

(2) 若$x,y\in B$，则 $(x),(xy)\in B$。

给定一个非空字符串$S$，其间 $S$ 只由两种字符(和)组成。

请你回答这个字符串是否属于 $B$。

标题大意

如标题描绘所示。

思路

首要咱们发现 $B$ 中的元素一定是匹配的括号序列，能够先用栈将非法的括号序列排查出去。

然后咱们观察到标题中说到：

若$x,y\in B$，则 $(x),(xy)\in B$。

这就告诉咱们一个事实，即：

若$x,y,z\in B$，则 $(xyz)\notin B$。

咱们利用括号的包括关系建树，假设 $a,b,c$ 均为合法的括号序列，若 $a$ 直接包括 $b$，即 $a=(b)$ 或者 $a=(bc)$，就使 $a$ 成为 $b$ 的父节点。

在这种规则下，$B$ 中元素发生的树一定是一个连通的二叉树。并且由集合 $B$ 的界说，一个连通的二叉树对应的括号序列一定是 $B$ 的子集。

那么具体怎样建树呢？

咱们首要记载给每个括号取一个姓名，并在左右括号都加以记载。每当咱们遇到一个左括号 $i$ 时，假如 $i$ 的左面紧挨着一个左括号，那么他是 $i$ 的父节点；假如 $i$ 的左面紧挨着一个右括号，那么他是 $i$ 的兄弟节点，他的父节点是 $i$ 的父节点。

完结建树后，咱们只需要判别整棵树是否连通、每个节点的子节点数量是否大于 $2$ 即可。

为了方便的判别树是否连通，我使得全场第一个左括号以 $0$ 作为其父节点，这样的话只需要判别 $0$ 的子节点数量是否是 $1$ 即可判别整棵树是否连通。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=300005;
char a[N];
int n,flag,id[N],bel[N],stk[N],t,tot,cnt[N];
int solve()
{
	for (int i=0;i<=n;++i) bel[i]=0,cnt[i]=0;
	scanf(" %s",a+1);
	n=strlen(a+1);
	flag=1;
	t=tot=0;
	for (int i=1;i<=n;++i)
	{
		if (a[i]=='(') id[i]=stk[++t]=++tot;
		else
		{
			if (t<1) return 0;
			id[i]=stk[t--];
		}
	}
	if (t!=0) return 0;
	for (int i=2;i<=n;++i)
	{
		if (a[i]!='(') continue;
		if (a[i-1]=='(') cnt[bel[id[i]]=id[i-1]]++;
		else cnt[bel[id[i]]=bel[id[i-1]]]++;
	}
	if (cnt[0]) return 0;
	for (int i=1;i<=n;++i)
		if (cnt[i]>2) return 0;
	return 1;
}
int main()
{
	int T;
	for (scanf("%d",&T);T--;) 
		if (solve()) printf("YES\n");
		else printf("NO\n");
	return 0;
}