「AGC 027C」ABland Yard

发表于 | | 阅读次数:
字数统计: 572 字

Description

题目链接：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。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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);
    while(m--) {
        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;
}
0%