글 읽기 - find_union() 함수와 make_union() 함수 부분에서 ..

skseofhek 4년 전 0

find_union(int v1, int v2) : v1, v2 정점이 서로 연결되어있는 지를 비교

make_union(int v1, int v2) : v1, v2의 _union[] 배열 업데이트

이런식으로 해주면 _union[] 배열이 항상 연결되어 있는 정점들중에서

가장 번호가 작은 정점을 나타낸다고 생각하는데..

혹시 잘못된 부분이 있나요...?

#include <iostream>
#include <queue>

using namespace std;

struct pos{
    int v1, v2, w;
};

int V, E, ret, tnum, tw;

priority_queue<struct pos> pq;
int _union[10001];
bool check[10001];

bool operator<(struct pos a, struct pos b)
{
    if(a.w > b.w) return 1;
    else return 0;
}

bool find_union(int v1, int v2)
{
    if(_union[v1] == _union[v2]) return 1;
    else return 0;
}

void make_union(int v1, int v2)
{
    if(_union[v1] < _union[v2])
    {
        for(int i=1; i<=V; i++)
        {
            if(_union[i] == _union[v2])
            {
                _union[i] = _union[v1];
            }
        }
    }
    else
    {
        for(int i=1; i<=V; i++)
        {
            if(_union[i] == _union[v1])
            {
                _union[i] = _union[v2];
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>V>>E;
    struct pos tPos;
    for(int i=0; i<E; i++)
    {        
        cin>>tPos.v1>>tPos.v2>>tPos.w;

        pq.push(tPos);
    }

    for(int i=1; i<=V; i++)
        _union[i] = i;

    long long int tret = 0;
    while(!pq.empty())
    {
        tPos = pq.top();
        //cout<<"v "<<tPos.v1<<' '<<tPos.v2<<"\n";
        pq.pop();

        if(!find_union(tPos.v1, tPos.v2))
        {
            tret += (long long int)tPos.w;
            make_union(tPos.v1, tPos.v2);

        }
    }

    cout<<tret<<"\n";


    return 0;
}

sait2000 4년 전 1

i가 v2가 되는 순간 어떻게 될까요? 그 다음에 v2랑 같은 그룹이었던 정점이 나오면 어떻게 될까요?

        for(int i=1; i<=V; i++)
        {
            if(_union[i] == _union[v2])
            {
                _union[i] = _union[v1];
            }
        }

skseofhek 4년 전 0

아...!!!

감사드립니다!!!!.

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

문제

문제

출처

ICPC

find_union() 함수와 make_union() 함수 부분에서 ..

skseofhek 4년 전 0

sait2000 4년 전 1

skseofhek 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말