题目描述

难度分：$1500$

输入$n(2 \leq n \leq 3 \times 10^5)$，$m(1 \leq m \leq 3 \times 10^5)$和$m$个数对$(a[i],b[i])$，元素范围 $[1,n]$且$a[i] \neq b[i]$。

能否找到两个数$x$和$y$，使得每个数对中至少有一个数是$x$或者是$y$？

输出YES或NO。

输入样例$1$

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例$1$

NO

输入样例$2$

5 4
1 2
2 3
3 4
4 5

输出样例$2$

YES

输入样例$3$

300000 5
1 2
1 2
1 2
1 2
1 2

输出样例$3$

YES

算法

BFS

依题意，如果有解，$x$必定在$a[1]$或者$b[1]$之中，分别尝试一下即可。假设$x=a[1]$，然后从$i=1$开始进行BFS，每次检查下一个数对$(a[i+1],b[i+1])$中有没有$x$：

1. 有就直接跳过，说明截止到目前为止，所有数对都可以被$x$覆盖掉（数对中只要有$x$或$y$就称为被覆盖）。
2. 没有就说明$a[i+1]$和$b[i+1]$中有一个是$y$，分别尝试一下。

这时候我们发现状态是不够的，在BFS的过程中应该记录截止到目前为止经过了几个不同的数，可以让队列存储二元组（数对编号$i$，截止到数对$i$经过的数字集合）。因此，只要可以遍历到$i=m$，并且在这个过程中集合的大小都没有超过过$2$，说明所有数对都可以被集合中的两个数给覆盖掉，输出YES即可；如果没有遇到过这种情况，就在BFS遍历完成后输出NO。

最后还需要注意一点的就是$CodeForces$卡哈希！

复杂度分析

时间复杂度

本质上是用BFS遍历$m$个数对，时间复杂度是$O(m)$的。

空间复杂度

队列中存储的二元组可以看成是$O(1)$的，因为我们可以控制集合的大小不超过$2$，这样二元组中最多只有三个元素。而BFS的额外空间复杂度是$O(m)$的，因此算法整体的额外空间复杂度也是$O(m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;
const int N = 300010;
int n, m, a[N], b[N];

bool bfs(queue<pair<int, set<int>>>& q) {
    while(!q.empty()) {
        auto cur = q.front();
        q.pop();
        int i = cur.first;
        auto& st = cur.second;
        int sz = st.size();
        if(i == m) return true;
        i++;
        if(st.count(a[i]) || st.count(b[i])) {
            q.push({i, st});
        }else {
            if(sz == 1) {
                set<int> st1 = {st.begin(), st.end()}, st2 = {st.begin(), st.end()};
                st1.insert(a[i]);
                st2.insert(b[i]);
                q.push({i, st1});
                q.push({i, st2});
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &a[i], &b[i]);
    }
    queue<pair<int, set<int>>> q;
    q.push({1, {a[1]}});
    if(bfs(q)) {
        puts("YES");
    }else {
        while(!q.empty()) q.pop();
        q.push({1, {b[1]}});
        if(bfs(q)) puts("YES");
        else puts("NO");
    }
    return 0;
}