文章目录
题目题解代码
题目
题目描述 一个国家有n个城市，城市之间连接着双向航空线路。一位疯狂的航空公司总裁Ronald Krump经常改变航班时刻表。更准确地说，他每天都做以下事情：
●选择其中一个城市
●如果该城市和某个其他城市之间之前没有航线那么在这两个城市之间创建一条航线，如果该城市和某个其他城市之间之前已有航线那么取消这条航线
例如，如果从城市5有航线通往城市1和2，但没有航线通往城市3和4，那么在Krump选择城市5并进行操作后，将有从城市5通往城市3和4的航线，但没有从城市5通往城市1和2的航线。
这个国家的公民在想，是否有一天航线图会变为完全图。换言之，当天任意两个不同的城市之间存在一条航线（直达）。写一个程序，根据当前的航线图，确定是否有可能有某一天出现这种情况，通过Krump的操作。
输入 第一行输入包含一个整数N（2≤N≤1000）。表示城市的数量。城市从1到N编号。 第二行输入包含一个整数M（0≤M≤N*（N-1）/2）。表示当前航线的数量。 接下来M行每行包含两个不同的整数，表示一条航线连接的两个城市的编号。
输出 如果有一天航线图会变为完全图，那么输出“DA”。否则输出“NE”。输出均不含引号。
样例输入 2 0
样例输出 DA
题解
吐槽特朗普，搞事搞到信息竞赛来了emmm…
先给结论：如果给出的图是一个完全图或者两个完全图，那么符合题意，反之则不符合
我们可以分成几个子命题来证明： 子命题一：一个完全图符合题意 子命题二：两个完全图符合题意 子命题三：三个及以上完全图不符合题意
子命题一证明 这个跳过
子命题二证明 假设当前有两个完全图
G
1
G1
G1和
G
2
G2
G2，如果我们选择
G
1
G1
G1中的一个节点
p
p
p，那么
p
p
p会和
G
2
G2
G2组成一个新的完全图，
G
1
G1
G1中剩下的点依然是一个完全图
子命题三证明 举个栗子，再自己思考一下，很简单的
玄学结论到手，码代码就很简单了。方法有很多，我用并查集水过了
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std
;
template <typename T
>
T
Fabs(T x
) {return x
< 0 ? -x
: x
;}
template <typename T
>
T
Max(T x
, T y
) {return x
> y
? x
: y
;}
const int N
= 1005;
vector
<int> G
[N
];
int n
, m
, a
, b
, cnt
;
int fa
[N
], d
[N
];
void makeSet(int x
) {
for(int i
= 1; i
<= x
; i
++)
fa
[i
] = i
;
}
int findSet(int x
) {
if(fa
[x
] != x
)
fa
[x
] = findSet(fa
[x
]);
return fa
[x
];
}
void unionSet(int x
, int y
) {
int u
= findSet(x
), v
= findSet(y
);
fa
[u
] = v
;
}
int main() {
freopen("ronald.in", "r", stdin);
freopen("ronald.out", "w", stdout);
scanf("%d%d", &n
, &m
);
makeSet(n
);
for(int i
= 1; i
<= m
; i
++) {
scanf("%d%d", &a
, &b
);
unionSet(a
, b
);
d
[a
] ++, d
[b
] ++;
}
for(int i
= 1; i
<= n
; i
++)
if(fa
[i
] == i
) {
cnt
++;
for(int j
= 1; j
<= n
; j
++)
if(findSet(j
) == findSet(i
))
G
[cnt
].push_back(j
);
}
if(cnt
> 2) {
printf("NE\n");
return 0;
}
for(int i
= 1;i
<= cnt
; i
++) {
int siz
= G
[i
].size();
bool f
= 1;
for(int j
= 0; j
<= siz
- 1; j
++)
if(d
[G
[i
][j
]] != siz
- 1) {
f
= 0;
break;
}
if(! f
) {
printf("NE\n");
return 0;
}
}
printf("DA\n");
return 0;
}
