AGC027C 题解

adam01 / 2024-08-06 / 原文

注意到如果可以构造出所有由 $\texttt{A}$ 和 $\texttt{B}$ 组成的字符串，那么在图上游走的路径必须成环，并且的环上的每一个点都必须同时有一个 $\texttt{A}$ 邻居和 $\texttt{B}$ 邻居。

于是可以考虑把点拆分为入点和出点，相邻两个点为 $\texttt{AA},\texttt{BB}$ 的，从入点向出点连边，否则出点向入点连边。

如果新图有环证明有解，否则无解。

这样就限制环上两个点之间一定是相同，不相同，相同，$\cdots$ 循环，满足条件。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 4e5 + 5;
vector<int> e[N];
int a[N], n, m;

int vis[N];
bool dfs(int x, int fa)
{
    vis[x] = 1;
    for(int i : e[x])
    {
        if(vis[i] == 1) return 1;
        if(!vis[i] && dfs(i, x)) return 1;
    }
    vis[x] = -1;
    return 0;
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    string s; cin >> s;
    for(int i = 1; i <= n; i ++) a[i] = s[i - 1] == 'B';
    for(int i = 1; i <= m; i ++)
    {
        int x, y; cin >> x >> y;
        if(a[x] != a[y]) e[x + n].push_back(y), e[y + n].push_back(x);
        else e[x].push_back(y + n), e[y].push_back(x + n);
    }
    for(int i = 1; i <= n * 2; i ++)
        if(!vis[i] && dfs(i, 0))
            return cout << "Yes\n", 0;
    cout << "No";

    return 0;
}

注意到没必要这么麻烦，因为一个点不满足同时有一个 $\texttt{A}$ 邻居和 $\texttt{B}$ 邻居，那么一定不在环上，所以可以删去这个点，然后更新邻居是否满足要求，是否加入队列即可。

是不是和拓扑排序很像？

按照拓扑排序的方法来写就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
vector<int> e[N];
int a[N], n, m;
int deg[2][N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    string s; cin >> s;
    for(int i = 1; i <= n; i ++) a[i] = s[i - 1] == 'B';
    for(int i = 1; i <= m; i ++)
    {
        int x, y; cin >> x >> y;
        e[x].push_back(y), e[y].push_back(x);
        deg[a[y]][x] ++;
        deg[a[x]][y] ++;
    }
    queue<int> q;
    int cnt = 0;
    for(int i = 1; i <= n; i ++)
        if(!deg[0][i] || !deg[1][i])
            q.push(i), cnt ++;
    while(q.size())
    {
        int t = q.front(); q.pop();
        for(int i : e[t])
        {
            if(!deg[0][i] || !deg[1][i]) continue;
            if(--deg[a[t]][i] == 0) q.push(i), cnt ++;
        }
    }
    if(cnt != n) cout << "Yes", 0;
    else cout << "No";

    return 0;
}