글 읽기 - c++ 100%에서 틀렸습니다..

didtmdqlsdl 2년 전 0

find_union으로 구현해서 입력 받은 노드를 연결하고

마지막에 parent 집합에 있는 값에 find를 적용한 값을 집합에 넣어서

집합의 개수를 구하는 방법으로 구현했는데 100%에서 틀렸습니다가 나오네요..

고수님들 도움 부탁드립니다!

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int N, M;
int parent[1001];
vector<pair<int, int> > v;

int Find(int x)
{
    if (parent[x] == x)
        return x;
    else
        return parent[x] = Find(parent[x]);
}

bool SameParent(int x, int y)
{
    int p1 = Find(x);
    int p2 = Find(y);
    if (p1 == p2)
        return true;
    else
        return false;
}

void Union(int x, int y)
{
    int p1 = Find(x);
    int p2 = Find(y);
    if (x < y)
        parent[y] = p1;

    else
        parent[x] = p2;
}

int main()
{
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        parent[i] = i;
    }

    for (int i = 1; i <= M; i++)
    {
        int input1, input2;
        cin >> input1 >> input2;
        v.push_back(make_pair(input1, input2));
    }

    for (int i = 0; i < v.size(); i++)
    {
        if (SameParent(v[i].first, v[i].second) == false)
        {
            Union(v[i].first, v[i].second);
        }
    }

    set<int> check;
    for (int i = 1; i <= N; i++)
    {
        check.insert(Find(i));
    }

    printf("%d", check.size());
    return 0;
}

dkvltmxhf 2년 전 0

Union 연산 할 때 비교와 parent를 바꿔주는 작업 모두 x와 y가 아닌 p1과 p2로 해주어야합니다.

아닐경우

parent[1] = 1

parent[2] = 2

parent[3] = 2

인 상태에서

Union(1,3) 이후 Find(2)를 하면 2의 부모는 바뀌지 않는 상태가 되어버립니다.

didtmdqlsdl 2년 전 0

감사합니다!!!!!

제가 잘못 알고있었네요 ㅎㅎㅎ

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

문제

문제

출처

ICPC

c++ 100%에서 틀렸습니다..

didtmdqlsdl 2년 전 0

dkvltmxhf 2년 전 0

didtmdqlsdl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말