글 읽기 - 어떤 부분이 틀렸을까요 ?

whwoals21 3년 전 0

반례도 못 찾겠고 어떤부분이 잘 못된건지 몰라 구글링을 해 봤습니다.

로직은 구글에 나온 정답과 모두 동일합니다

제거되지 않는 간선은 놔두고 (merge 상태로), 제거할 간선을 역순으로 (저같은경우 스택을 활용하여 역으로 출력) 하나씩 Merge 하며 집합의 크기를 곱하여 답에 더해주는 식으로 했습니다.

여러 풀이를 보니 저는 부모를 갖는 parent 배열과 그 집합의 크기를 갖는 sz 배열 두가지를 활용하였는데 많은분들이 P배열 하나만을 사용하여 풀이한것을 보았습니다.

코딩의 차이일뿐 실제 정답을 내는데 차이를 만들지는 않는것 같은데 제 코드는 어디가 잘못 된건지 궁금합니다.

감사합니다.

#include <iostream>
#include <stack>

using namespace std;
#define MAX 100001
#define ll long long
int N, M, Q, X, Y, A;
int parent[MAX];
ll sz[MAX];
pair<pair<int, int>, bool> edge[MAX];
stack<int> process;
ll ans;

void init() {
    for (int i = 1; i <= M; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

int find(int a) {
    if (parent[a] == a)
        return parent[a];
    return parent[a] = find(parent[a]);
}

void merge(int a, int b) {
    int aa = find(a);
    int bb = find(b);

    if (aa == bb) return;

    if (sz[aa] > sz[bb]) { // aa 가 더 큰 집합
        parent[bb] = aa;
        sz[aa] += sz[bb]; // aa집합에 크기를 더해주고 
        sz[bb] = 1; // bb 집합의 크기는 이제 1 
    } else {
        parent[aa] = bb;
        sz[bb] += sz[aa];
        sz[aa] = 1;
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> Q;
    init();
    for (int i = 1; i <= M; i++) {
        cin >> X >> Y;
        edge[i] = {{X, Y}, true};
    }
    for (int i = 0; i < Q; i++) {
        cin >> A;
        edge[A].second = false; // 사용 안되는걸로 변경
        process.push(A); // 자를 (합칠) 간선들을 stack에 넣어서 역순으로 계산하기 위해
    }
    for (int i = 1; i <= M; i++) {
        if (edge[i].second == false) continue;
        int a = edge[i].first.first;
        int b = edge[i].first.second;
        merge(a, b);
    }
    while (!process.empty()) { // 스택을 이용해 
        int step = process.top(); // 맨 마지막 단계
        int pa = find(edge[step].first.first);
        int pb = find(edge[step].first.second);
        process.pop();
        if (pa != pb)  // 서로 다른 집합 관계다
            ans += (sz[pa] * sz[pb]);
        merge(pa, pb);
    }
    cout << ans << '\n';
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 부분이 틀렸을까요 ?

whwoals21 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말