题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$表示$n$块骨牌，每块骨牌上写有两个数。

然后输入$n$行，每行$2$个数，表示骨牌上的数字，范围$[1,n]$。

你需要把这$n$块骨牌分成两组，使得每组内都不含重复数字。

能否做到？输出YES或NO。

例如有$4$块骨牌：$(1,4),(1,3),(3,2),(4,2)$。可以分成如下两组：

• 第一组：$(1,4),(3,2)$。
• 第二组：$(1,3),(4,2)$。

输入样例

6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8

输出样例

YES
NO
NO
YES
YES
NO

算法

二分图

构建一个映射“数字 $\rightarrow$ 该数字出现的骨牌编号”$node2idx$。很显然，一个数字只要出现在两张以上的骨牌上，分组绝对无法完成，其余情况就是个二分图的问题了。

遍历$node2idx$的键值对，只要某个数字存在于两张骨牌$x$和$y$上，那么$x$和$y$之间就连边。接下来对整张图跑染色法就行，只要能构成二分图，分组就是可以完成的。

复杂度分析

时间复杂度

本质上就是建图之后跑染色法，看能否构成二分图。染色法的需要遍历整张图的所有节点和边，因此时间复杂度为$O(n+m)$，其中$n$为节点数，$m$为边数。

空间复杂度

颜色数组$c$的空间复杂度为$O(n)$，图的邻接表$graph$空间复杂度为$O(n+m)$，$node2idx$映射表的空间复杂度也为$O(n)$。在最差情况下，染色法的递归深度也是$O(n)$，所以整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
const int N = 200010;
typedef pair<int, int> PII;
int n, a[N], b[N], c[N];
unordered_map<int, vector<int>> graph;

bool dfs(unordered_map<int, vector<int>>& graph, int u, int x) {
    c[u] = x;
    for(int v: graph[u]) {
        if(c[v] == -1) {
            dfs(graph, v, 1 - x);
        }else {
            if(c[v] == x) return false;
        }
    }
    return true;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        vector<PII> tup;
        unordered_map<int, vector<int>> node2idx;
        bool flag = true;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);
            node2idx[a[i]].push_back(i);
            node2idx[b[i]].push_back(i);
            if(node2idx[a[i]].size() > 2 || node2idx[b[i]].size() > 2) flag = false;
        }
        if(!flag) {
            puts("NO");
            continue;
        }
        graph.clear();
        for(auto&[k, v]: node2idx) {
            if(v.size()) {
                graph[v[0]].push_back(v[1]);
                graph[v[1]].push_back(v[0]);
            }
        }
        for(int i = 1; i <= n; i++) c[i] = -1;
        for(int i = 1; i <= n; i++) {
            if(c[i] == -1) {
                if(!dfs(graph, i, 0)) {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}