Description

AGC027C

给定一张图，点有标号A或B，计算是否对于任意的一个由AB构成的字符串都在图中有对应的路径。

Solution

观察可以发现，如果有个环（不一定是简单环）是AABB的无限循环，就输出Yes，否则输出No。

UPD:对于上面那个结论，这里给出简要证明：当在这个环上任意一个A点时，可以任意的走向AB点，在任意一个B点时也是这样，那么，对于任意字符串，只需走向要求的点即可。

然鹅，话是这么说，码却没有那么好写，我一开始写了dfs找环，但是一直WA，和标程对拍也拍不出来错。所以我就换了一种思路，借用拓扑排序的思想，每次将只与一种字符相连的点删去，如果删完还剩下，那么就说明有一个AABB的环，否则就没有。

Code

拓扑排序版：

#include <cstdio>

const int N = 2e5 + 10;

const int M = 4e5 + 10;

int hd[N], nxt[M], to[M], cnt;

int deg[N][2];

int n, m;

char col[N];

int q[N], qhd, qtl, vis[N];

inline void adde(int x, int y) {

	cnt++;

	to[cnt] = y; nxt[cnt] = hd[x];

	hd[x] = cnt;

}

int main() {

	scanf("%d%d", &n, &m);

	scanf("%s", col+1);

	for (int i = 1, x, y; i <= m; ++i) {

		scanf("%d%d", &x, &y);

		adde(x, y);

		adde(y, x);

		deg[x][col[y] == 'B']++;

		deg[y][col[x] == 'B']++;

	}

	for (int i = 1; i <= n; ++i) {

		if (deg[i][0] == 0 || deg[i][1] == 0) vis[q[qtl++] = i] = 1;

	}

	while (qhd != qtl) {

		int x = q[qhd++];

		// printf("%d\n", x);

		// vis[x] = 1;

		for (int i = hd[x]; i; i = nxt[i]) if (!vis[to[i]]) {

			if (--deg[to[i]][col[x] == 'B'] == 0) {

				vis[to[i]] = 1;

				q[qtl++] = to[i];

			}

		}

	}

	if (qtl == n) puts("No");

	else puts("Yes");

}

巴特西

[AGC027C]ABland Yard

Description

Solution

Code

最新文章

热门文章