글 읽기 - weighted union find를 이용했는데 실패원인을 모르겠네요

icosang 1년 전 0

예제 입력이나, 다른 경우를 손으로 테스트해봐도 잘 나오는데, 어떤 부분에 오류가 있어

실패하는 것인지 찾기 어려워 질문드립니다

#include <stdio.h>
#include <iostream>
#include <map>
#include <string.h>
#define MAX_SIZE 2000007

using namespace std;

int parent[MAX_SIZE];

int find(int x, bool findScale = false) {
    if (parent[x] < 0) {
        if (findScale) return -parent[x];
        return x;
    }
    else {
        if (findScale) return find(parent[x], true);

        int y = find(parent[x]);
        parent[x] = y;
        return y;
    }
}

void Union(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y)
        return;

    if (parent[x] < parent[y]) {
        parent[x] += parent[y];
        parent[y] = x;
    }
    else {
        parent[y] += parent[x];
        parent[x] = y;
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    int a;
    scanf("%d", &a);

    for (int i = 0; i < a; i++) {
        int b;
        scanf("%d", &b);
        int idx = 1;
        memset(parent, -1, sizeof(parent));
        map<string, int> name;

        for (int j = 0; j < b; j++) {
            string s1, s2;
            int c, d;

            cin >> s1 >> s2;

            if (name.count(s1) == 0)
            {
                name[s1] = idx++;
            }

            if (name.count(s2) == 0)
            {
                name[s2] = idx++;
            }

            c = name[s1];
            d = name[s2];

            Union(c, d);
            printf("%d\n", find(d, true));
        }
    }
}

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

문제

문제

출처

ICPC

weighted union find를 이용했는데 실패원인을 모르겠네요

icosang 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말