AT_abc327_d题解

ilibilib · 2023-11-05 10:09:06 · 题解

题目大意：

给定一个由不超过 N 的正整数组成的长度为 M 的数列对 (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)) 。如果数列对 (S, T) 满足以下条件，则称其为 好的数列对：

• 存在一个由 0 和 1 构成的长度为 N 的数列 X = (X_1, X_2, \dots, X_N) ，满足以下条件：
  • 对于每个 i = 1, 2, \dots, M ，有 X_{S_i} \neq X_{T_i} 。

给定长度为 M 的数列对 (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)) ，请判断 (A, B) 是否是一个好的数列对，如果是则输出 Yes，否则输出 No。

题目分析：

dfs+染色。

建双向边。

用 dfs 遍历。

一个点遍历到的下一个点的颜色一定与它相反。

如果它已经被遍历过了，判断是否满足上述条件。

如果没有被遍历过，按照上述条件进行染色，并 dfs 这个点。

#include<bits/stdc++.h>
#define N 400010
using namespace std;
int a[N],b[N];
bool bl[N],f[N];//bl记录是否被记录,f记录颜色
struct qxx{int nx,to;}tu[N];int hd[N],bs=0;
bool dfs(int u)
{
    bl[u]=true;
    for(int i=hd[u];i;i=tu[i].nx)
    {
        int v=tu[i].to;
        if(bl[v]) {if(f[v]==f[u]) return true;}//该点已经被染色,但颜色相同,返回
        else {f[v]=!f[u]; if(dfs(v)) return true;}//该点未被染色,进行染色,并且遍历这个点
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i) cin>>a[i];
    for(int i=1;i<=m;++i) cin>>b[i];
    for(int i=1;i<=m;++i)
        tu[++bs]={hd[a[i]],b[i]},hd[a[i]]=bs,
        tu[++bs]={hd[b[i]],a[i]},hd[b[i]]=bs;
    for(int i=1;i<=n;++i)
        if(!bl[i]) if(dfs(i)) {puts("No");return 0;}//遍历每个点
    puts("Yes");
    return 0;
}