Siyuan

「AGC 027C」ABland Yard
「AGC 027C」ABland Yard
扫描右侧二维码阅读全文
23
2018/11

「AGC 027C」ABland Yard

题目链接:AGC 027C

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

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


Solution

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

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

  • 如果环内连续的 AB 的个数小于 $2$,那么无法构成 AABB
  • 如果环内连续的 AB 的个数大于 $2$,那么必然存在一个结尾为 ABBABAAB 的串无法构成。

如果我们 $\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;
}
最后修改:2019 年 06 月 28 日 12 : 47 PM

发表评论