반응형

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

 

4343번: Arctic Network

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt를 선언합니다.

 

2. vect[ i ] = i로 초기화하고, 각 지점까지의 거리를  arr 배열에 저장합니다.

 

3. arr 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 각 지점들을 연결하고, 연결될 때마다 cnt++를 해주고, cnt == P - S일 때 거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int u, v;
    double d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int T, S, P;
vector<node> arr;
pair<int, int> pos[501];
int vect[501];
int cnt;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    cout << fixed;
    cout.precision(2);
 
    for (int t = 0; t < T; t++) {
        cin >> S >> P;
 
        arr.clear();
        cnt = 0;
 
        for (int i = 1; i <= P; i++) {
            int x, y;
            cin >> x >> y;
            pos[i] = { x,y };
            vect[i] = i;
        }
 
        for (int i = 1; i <= P - 1; i++) {
            for (int j = i + 1; j <= P; j++) {
                int x = pos[i].first - pos[j].first;
                int y = pos[i].second - pos[j].second;
                double d = sqrt(x * x + y * y);
                arr.push_back({ i,j,d });
            }
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        for (auto& next : arr) {
            const int u = next.u;
            const int v = next.v;
            const double d = next.d;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                cnt++;
            }
 
            if (cnt == P - S) {
                cout << d << '\n';
                break;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
반응형

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

 

17398번: 통신망 분할

첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt 배열을 선언합니다.

 

2. vect[ i ] = i, cnt[ i ] = 1 로 초기화합니다.

 

3. 끊을 연결들을 stack에 저장합니다.

 

4. 끊을 연결들을 제외하고 나머지 연결들을 Union-Find를 이용하여 연결해 줍니다.

 

5. 끊을 연결들을 stack에서 하나씩 빼서 연결해 주면서 ans에 끊어진 연결들을 곱해 더해줍니다.

 

6. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<stack>
#define ll long long
 
using namespace std;
 
int N, M, Q;
int visited[100001];
int vect[100001];
ll cnt[100001];
pair<int, int> arr[100001];
stack<int> edge;
 
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;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &Q);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 0; i < Q; i++) {
        int A;
        scanf("%d", &A);
        edge.push(A - 1);
        visited[A - 1] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        if (visited[i] != 1) {
            if (Find(arr[i].first) != Find(arr[i].second)) {
                Union(arr[i].first, arr[i].second);
            }
        }
    }
 
    ll ans = 0;
 
    while(!edge.empty()){
        int a = arr[edge.top()].first;
        int b = arr[edge.top()].second;
        edge.pop();
 
        if (Find(a) != Find(b)) {
            ans += (cnt[Find(a)] * cnt[Find(b)]);
            Union(a, b);
        }
    }
 
    printf("%lld\n", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
반응형

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

 

16168번: 퍼레이드

첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. 퍼레이드 이동이 가능한 경우는 한 붓 그리기가 가능한 경우이므로 한 붓 그리기가 가능한 지 그래프를 그려 판단합니다.

 

4. 연결된 간선의 수가 홀수인 노드의 개수가 0개 또는 2개일 경우에만 한 붓 그리기가 가능하므로 해당 조건을 만족하는 경우 모든 노드가 연결되어 있다면 YES를 출력하고, 그렇지 않다면 NO를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int V, E;
int vect[3001];
vector<int> list[3001];
 
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", &V, &E);
 
    for (int i = 1; i <= V; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < E; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        list[a].push_back(b);
        list[b].push_back(a);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
    }
 
    int cnt = 0;
    int temp = Find(1);
 
    if (list[1].size() % 2 == 1) cnt++;
 
    for (int i = 2; i <= V; i++) {
        if (list[i].size() % 2 == 1) cnt++;
 
        if (cnt > 2 || temp != Find(i)) {
            printf("NO");
            return 0;
        }
    }
 
    printf("YES");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
반응형

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

 

15789번: CTP 왕국은 한솔 왕국을 이길 수 있을까?

입력의 첫째 줄에 왕국의 수 N(3 ≤ N ≤ 100,000)과 동맹 관계의 수 M(1 ≤ M ≤ 200,000)이 주어진다. 이 후 M개의 줄에 X,Y가 주어진다. 이는 X 왕국과 Y 왕국이 동맹이라는 뜻이다. 입력의 마지막 줄에 CT

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 왕국을 이어주고, 이을 때마다 power 배열에 값을 경신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 CTP 왕국이나 한솔 왕국에 속하지 않은 왕국들의 동맹국들의 수를 ans 배열에 저장합니다.

 

5. ans 배열을 내림차순으로 정렬하고, K개까지 동맹국을 더해줍니다.

 

6. 그 결과를 출력합니다.

 

[ 소스코드 ]

 

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
int vect[100001];
int power[100001];
int visited[100001];
vector<int> ans;
 
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;
    power[pa] += power[pb];
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        power[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int X, Y;
        scanf("%d %d", &X, &Y);
 
        if (Find(X) != Find(Y)) {
            Union(X, Y);
        }
    }
 
    int C, H, K;
    scanf("%d %d %d", &C, &H, &K);
    int cnt = 0;
 
    if (K) {
        for (int i = 1; i <= N; i++) {
            int temp = Find(i);
            if ((Find(C) != temp) && (temp != Find(H))) {
                if (visited[temp] == 0) {
                    visited[temp] = 1;
                    ans.push_back({ power[temp] });
                }
            }
        }
    }
 
    sort(ans.begin(), ans.end(), greater<>());
 
    int temp = power[Find(C)];
 
    for (int i = 0; i < min((int)ans.size(), K); i++) {
        temp += ans[i];
    }
    printf("%d", temp);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
반응형

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

 

14595번: 동방 프로젝트 (Large)

첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. x와 y의 부모노드가 다르다면 y부터 x까지 for문을 통해 돌면서 x와 y사이에 있는 모든 동방들을 x와 이어줍니다. 이때, j = Find( j ) 를 통해 j를 갱신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 부모노드가 다르면 ans++를 해줍니다.

 

5. ans를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[1000001];
int visited[1000001];
 
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);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int x, y;
 
        scanf("%d %d", &x, &y);
 
        if (Find(x) != Find(y)) {
            for (int j = y; j > x; j--) {
                j = Find(j);
                Union(x, j);
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        if (visited[Find(i)] == 0) {
            visited[Find(i)] = 1;
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
반응형

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

 

20955번: 민서의 응급 수술

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 뉴런을 이어주고, 이미 이어져 있다면 ans++를 해줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 부모노드가 다르면 ans++를 해줍니다.

 

5. ans - 1을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[100001];
int ans;
int visited[100001];
 
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);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
        else {
            ans++;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[Find(i)] == 0) {
            visited[Find(i)] = 1;
            ans++;
        }
    }
 
    printf("%d", ans - 1);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
반응형

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

 

10723번: 판게아 1

첫 줄에는 테스트 케이스의 수 \(T\)가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 \(n\)과 도로가 건설된 횟수 \(m\)이 공백으로 구분되어 주어진다. 다음 \(n - 1\)줄에 태초

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 오름차순으로 정렬합니다.

 

3. 새로운 간선을 입력받을 때마다 mst를 새로 만들어 줍니다.

 

4. 3의 과정에서 새로운 간선이 이전의 mst의 가장 긴 간선보다 길다면 mst를 다시 만들어 줄 필요가 없으므로 넘어갑니다.

 

5. 만들어지는 모든 mst를 XOR 해 ans에 저장합니다.

 

6. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int u, v, c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int vect[100000];
vector<node> arr;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        arr.clear();
 
        for (int i = 1; i < n; i++) {
            int u, c;
            scanf("%d %d", &u, &c);
            arr.push_back({ i,u,c });
        }
 
        int Max = 987654321;
        ll temp = 0;
        ll ans = 0;
 
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
 
            arr.push_back({ u,v,c });
 
            if (Max > c) {
                temp = 0;
                Max = 0;
 
                for (int j = 0; j < n; j++) {
                    vect[j] = j;
                }
 
                sort(arr.begin(), arr.end(), cmp);
 
                for (auto& next : arr) {
                    const int u = next.u;
                    const int v = next.v;
                    const int c = next.c;
 
                    if (Find(u) != Find(v)) {
                        Union(u, v);
                        temp += c;
                        Max = max(Max, c);
                    }
                }
            }
            
            if (i == 0) {
                ans = temp;
            }
            else {
                ans ^= temp;
            }
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
반응형

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

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 내림차순으로 정렬합니다.

 

3. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 간선의 비용을  ans에 더해주고, 개수를 cnt에 저장합니다.

 

4. cnt가 N - 1이면 ans를 출력하고, 그렇지 않다면 -1을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, C;
};
 
bool cmp(node left, node right)
{
    return left.C > right.C;
}
 
int N, M;
node arr[20000];
int vect[1001];
 
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);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].A, &arr[i].B, &arr[i].C);
    }
 
    sort(arr, arr + M, cmp);
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int C = arr[i].C;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ans += C;
            cnt++;
        }
    }
 
    if (cnt != N - 1) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
반응형

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

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 간선의 개수를  ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int N, M;
int ans;
int vect[1001];
pair<int, int> arr[10000];
 
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()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &N, &M);
        ans = 0;
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &arr[i].first, &arr[i].second);
        }
 
        for (int i = 0; i < M; i++) {
            const int a = arr[i].first;
            const int b = arr[i].second;
 
            if (Find(a) != Find(b)) {
                Union(a, b);
                ans++;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15

+ Recent posts

티스토리툴바