백준 27945 - 슬슬 가지를 먹지 않으면 죽는다 (C++)

문제

• 문제 링크

  
   BOJ 27945 - 슬슬 가지를 먹지 않으면 죽는다 
  

• 문제 요약

$N$개의 정점을 잇는 $M$개의 간선 정보가 주어진다.
$1$일차부터 매일 노점에 들려야 할 때, 버틸 수 있는 가장 긴 날의 수를 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ N ≤ 10^5$

$N - 1 ≤ M ≤ min(5 * 10^5, {N\choose 2})$

$1 ≤ t_i ≤ 10^9$

알고리즘 분류

• 자료 구조(data structures)
• 그래프 이론(graphs)
• 분리 집합(disjoint_set)

풀이

모든 요리 학원에 다닐 수 있도록 $N - 1$ 개의 길을 고른다고 한다.
이 대목에서 유사 $mst$ 문제임을 눈치 챘다면 문제는 쉬워진다.

날짜가 $1$일차부터 시작하므로, 간선들을 $t_i$ 가 단조 증가 하도록 정렬하자.
그럼 결국 키위새가 쓰러지는 날은 다음과 같다.

임의의 간선에 대해,

• 지금까지 이어온 날과 연속적이지 않은 $t_i$가 튀어 나오거나
• 연속적인 $t_i$임에도 이미 $merge$ 된 요리 학원들을 잇는 경우

만약 위 조건에 한 번도 걸리지 않았다면 $d = N + 1$ 임을 유의하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct E
{
    int p, q, w;
    bool operator<(E& e) { return w < e.w; }
};
int n, m, r, P[100001];
 
int f(int p) { return P[p] = P[p] == p ? p : f(P[p]); }
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    iota(P, P + 100001, 0); cin >> n >> m;
    vector <E> Eg(m);
    for (auto& [p, q, w] : Eg) cin >> p >> q >> w;
    sort(Eg.begin(), Eg.end());
    for (auto& [p, q, w] : Eg)
    {
        int x(f(p)), y(f(q));
        if (++r ^ w || x == y) cout << r, exit(0);
        P[x] > P[y] ? P[x] = y : P[y] = x;
    }
    cout << r + 1;
}

comment

끝