Codeforces Round #745 (Div. 2)-B. Diameter of Graph

문제 설명

성훈은 정점의 수가 $n$이고, 간선의 수가 $m$이며 그래프의 지름이 $k - 1$보다 작은 무방향 연결 그래프를 그리고 싶다. 또한 그 그래프는 self-loop와 다중 간선이 없어야 한다. (즉 각 간선은 서로 다른 두 정점과 연결되어야 하며, 두 정점사이에는 반드시 한개의 간선이 있어야 한다.)

그래프의 지름은 두 노드를 무작위로 선택할 때, 그 노드 사이에서 가질 수 있는 최대 거리를 의미한다.

두 노드 사이의 거리는 두 노드를 양 끝점으로 했을 때 두 노드 사이에 연결된 최소 간선의 개수를 말한다.

성훈은 이러한 그래프를 그릴 수 있는지 없는지 알고 싶다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$이 주어진다.

각 테스트 케이스에는 세 정수 $n(1 \le n \le n^9), m, k(0 \le m,k \le 10^9)$ 가 주어진다.

Output
각 테스트 케이스마다 주어진 조건에 맞는 그래프를 그릴 수 있으면 "YES"를, 그릴 수 없으면 "NO"를 출력한다. 각 문자열은 대문자나 소문자 모두 상관 없다.

Example
input
5
1 0 3
4 5 3
4 6 3
5 4 1
2 1 1

output
YES
NO
YES
NO
NO

문제 접근

사용한 알고리즘: 그래프 이론, 수학
걸린 시간 : 00:10
이 문제에서 시간을 다 잡아먹고 결국 1솔로 끝나게한 열받는 문제이다. 트리와 그래프의 개념이 부족한 내 탓이라고 생각한다. 실제로 이 문제를 풀면서 트리와 그래프에서 정점과 간선의 관계를 훨씬 더 정확하게 이해할 수 있었다. 생각보다 얻어간 것이 많은 문제이니 꼭 한번 풀어보자.

주어진 조건을 따라 차근차근히 생각해보자. 조건을 나누는 문제는 급하게 하다가 나처럼 꼬이고 시간 다 잡아먹기 쉽상이니 침착한게 중요하다.

일단 연결 그래프를 그려야 하기 때문에 연결이 안된 그래프의 경우는 NO를 출력하면 된다. 그리고 이 조건은 $m < n - 1$ 일때 성립한다. 직접 그려보면 왜 그런지 알기 때문에 설명은 생략한다.
또한 두 정점 사이에서 간선이 여러개 있으면 안되는데, 정점이 $n$개 일때, 이 정점 사이에 모든 간선을 빈틈없이 이으면 간선이 총 $\frac{n \times (n - 1)}{2}$ 개가 필요하다. 그냥 $n$ 개 중 2개를 순서와 관계없이 선택하는 조합의 수와 같다. 그리고 이 수보다 간선 개수가 많다면 무조건 두 정점 사이 간선의 개수가 1개 이상이 되기 때문에 $m > \frac{n \times (n - 1)}{2}$ 또한 NO를 출력하면 된다.

즉 무조건 안되는 경우는

• $m < n - 1$
• $m > \frac{n \times (n - 1)}{2}$ 이다.

그리고 경계값을 비교하는 것이 조건 세는 문제의 핵심이기 때문에 경계값도 세준다.

1. $m = n - 1$ 일때는 그래프 중 트리 형태를 나타낸다. 하나의 정점을 루트로 놓고 나머지 정점에 하나씩 간선을 이으면 이 트리의 지름은 $2$가 된다. 그리고 이 지름이 $2$인 경우가 트리일 때 최소 지름의 수 이다. 따라서 $k > 3$ 일때 조건에 부합하므로 "YES"를, 아닐때는 "NO"를 출력한다.
2. $m = \frac{n \times (n - 1)}{2}$ 일때는 위에서 말했듯이 완전 연결 그래프를 만든다. 이 그래프는 모든 정점 사이에 간선이 하나씩 있기 때문에 지름이 $1$이다. 따라서 $k > 2$ 일때 조건에 부합하므로 "YES"를, 아닐때는 "NO"를 출력한다.
3. $n = 1$ 일 때는 경우를 따로 세줘야 하는데, 정점이 $1$개이면 지름이 0이기 때문에 $k > 1$ 일때 조건에 부합한다.

이 3가지 경우가 아니면 $n - 1< m < \frac{n \times (n - 1)}{2} $ 인 경우가 남았다. 이 경우는 위에서 말한 지름이 $2$인 트리를 만든 다음에 남은 간선을 하나씩 덧붙이면 지름이 최소인 그래프를 만들 수 있다. 그리고 그 그래프의 지름은 모든 노드가 완전히 연결이 안됐기 때문에 아직 지름은 트리와 같다. 따라서 지름은 $2$ 이다. 따라서 $k > 3$ 일때 조건에 부합한다.

이 모든 경우를 고려해서 조건문을 작성하면 그것이 문제의 답이다. 문제의 코드는 짧지만 경우의 수 세는 것이 좀 귀찮은 문제였다.

정답 코드

#include <iostream>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll n, m, k; cin >> n >> m >> k;
        ll tmp = n * (n - 1) * 1LL / 2;
        if(m < n - 1 || m > tmp) cout << "NO";
        else if(n == 1) cout << (k > 1 ? "YES" : "NO");
        else if(m == tmp) cout << (k > 2 ? "YES" : "NO");
        else cout << (k > 3 ? "YES" : "NO");
        cout << "\n";
    }
    return 0;
}