Problem
一个国家的 \(N\) 个城市通过双向航线相连。
规定一次操作为：
- 选定其中一个城市
- 开设该城市到其它所有城市的航线，同时取消该城市的原有航线
请问是否存在一种操作方式，使得每两个城市之间都存在直达航线（操作次数不限）。
\(2 \le N \le 1000\)，\(0 \le M \lt \dfrac{N(N-1)}{2}\)。
Input
第一行，一个整数 \(N\)，表示城市的数量。
第二行，一个整数 \(M\)，表示初始的航线数量。
接下来的 \(M\) 行，每行两个不相等的整数，表示该航线连接的两个城市。
Output
若存在符合题意的操作方式，则输出 DA。否则输出 NE。
Sample
Input 1
2
0
Output 1
DA
Input 2
3
2
1 2
2 3
Output 2
NE
Input 3
4
2
1 3
2 4
Output 3
DA
Solution
对于一个节点，容易发现只有操作奇数次和偶数次两种不同的状态。简化一下就是不操作和只操作一次两种情况。
于是可以考虑将每个点拆成两个点分别表示选和不选，然后建边跑并查集判是否为二分图即可。
如果原图两点间有边，两点要么都不反转，要么都反转；如果原图两点间没有边，两点间有且只有一点反转。
如果最后存在一个点使得该点拆出来的两个点属于同一个连通块，说明矛盾，否则有解。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 2005;
int n, m;
bool e[kmax][kmax];
int f[kmax];
int F(int x) {
return f[x] == x ? x : f[x] = F(f[x]);
}
void Merge(int x, int y) {
x = F(x), y = F(y);
f[x] = y;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n << 1; i++) { // 两倍节点
f[i] = i;
}
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
e[x][y] = e[y][x] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (e[i][j]) { // 两点之间有边
Merge(i, j); // 都不操作
Merge(i + n, j + n); // 都操作
} else {
Merge(i, j + n);
Merge(i + n, j); // 只操作其中一个点
}
}
}
for (int i = 1; i <= n; i++) {
if (F(i) == F(i + n)) { // 属于同一连通块
cout << "NE"; // 矛盾
return 0;
}
}
cout << "DA";
return 0;
}