题目链接：AGC 027C

给出一个 $n$ 个点，$m$ 条边的无向图（可能有自环）。每个节点有一个值 A 或 B，你可以从任意一个节点出发，经过一些节点后（可以重复经过）并将经过节点的值顺次写出来，就可以得到一个字符串。求是否满足对于任何一个满足只包含 A 或 B 的字符串都可以被这张图构造出来。

数据范围：$n,m\le 2\times 10^5$。

Solution

这题看上去不是很可做，所以我们可以猜测结论：一张图满足条件，当且仅当包含一个由 AA 和 BB 交替出现的环。

其实这个结论很好证明，我们考虑反证法：

• 如果环内连续的 A 或 B 的个数小于 $2$，那么无法构成 AA 或 BB。
• 如果环内连续的 A 或 B 的个数大于 $2$，那么必然存在一个结尾为 ABBA 或 BAAB 的串无法构成。

如果我们 $\text{DFS}​$ 找环，那么细节太多了我太懒了不想写，所以我们可以换一种思路，利用拓扑排序的思想，每次将只与一种字符相连的点删掉，那么剩下的点一定即和 A 相连又和 B 相连，代表 AABB 这样循环的串。因此如果所有点都删掉了，那么说明不满足条件输出 No，否则满足条件输出 Yes。

时间复杂度：$\mathcal O(n + m)$。

Code

#include <cstdio>
#include <queue>

const int N = 2e5 + 5, M = 4e5 + 5;

int n, m, tot, lnk[N], ter[M], nxt[M], deg[N][2];
char col[N];
bool vis[N];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
bool check() {
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) return 0;
    }
    return 1;
}
int main() {
    scanf("%d%d%s", &n, &m, col + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
        deg[u][col[v] == 'B']++;
        deg[v][col[u] == 'B']++;
    }
    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!deg[i][0] || !deg[i][1]) {
            q.push(i), vis[i] = 1;
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (vis[v]) continue;
            if (!--deg[v][col[u] == 'B']) {
                q.push(v), vis[v] = 1;
            }
        }
    }
    puts(check() ? "No" : "Yes");
    return 0;
}