반응형

https://www.acmicpc.net/problem/25545

 

25545번: MMST

첫째 줄에 그래프의 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 200\,000$, $N-1 \leq M \leq 500\,000)$ 둘째 줄부터 $M$줄에 걸쳐 $i$번째 간선의 정보가 $(U_i, V_i, C_i)$와 같이 주어진다. 이는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N > M 인 경우에는 스패닝 트리가 최대 하나밖에 나오지 않기 때문에 해당 경우에는 MMST가 나올 수 없습니다.

 

2. N <= M 인 경우에는 모든 간선의 길이가 다르기 때문에 스패닝 트리가 최소 3개가 있고  그렇기 때문에 MMST가 최소 1개 있습니다.

 

3. MST를 만들고 거기에 포함되지 않은 간선이 포함된 스패닝 트리는 무조건 MMST 가 되므로 이를 활용하여 MMST를 구합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct edge {
    int num;
    int from;
    int to;
    int dist;
};
 
bool Greater(edge left, edge right)
{
    return left.dist < right.dist;
}
 
bool Less(edge left, edge right)
{
    return left.dist > right.dist;
}
 
int N, M;
edge Edge[500000];
vector<int> ans;
int visited[500000];
int vect[200001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    if (N > M) {
        printf("NO");
        return 0;
    }
 
    for (int i = 0; i < M; i++) {
        int U, V, C;
        scanf("%d %d %d", &U, &V, &C);
        Edge[i] = { i + 1,U,V,C };
    }
 
    sort(Edge, Edge + M, Greater);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        const int a = Edge[i].from;
        const int b = Edge[i].to;
        const int num = Edge[i].num;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            visited[num] = 1;
        }
    }
    
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    int flag = false;
 
    for (int i = 0; i < M; i++) {
        const int num = Edge[i].num;
        if (visited[num] == 0) {
            ans.push_back(num);
            Union(Edge[i].from, Edge[i].to);
            break;
        }
    }
 
    for (int i = 0; i < M; i++) {
        const int a = Edge[i].from;
        const int b = Edge[i].to;
        const int num = Edge[i].num;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans.push_back(num);
        }
    }
 
    printf("YES\n");
    for (int num : ans) {
        printf("%d ", num);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27
[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26

+ Recent posts

티스토리툴바