핑크 플로이드 (feat. 백준, 6091번)

핑크 플로이드
https://www.acmicpc.net/problem/6091

6091번: 핑크 플로이드

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <stack>

#define INF 1e9
#define endl "\n"

typedef long long ll;
typedef double dd;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

using namespace std;

vector <pair <int , pii> > edges;
int parent[1025];
int n;

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

void unionNodes(int a, int b)
{
    int x = getParent(a);
    int y = getParent(b);

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


int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            int x; scanf("%d", &x);
            edges.push_back({x, {i, j}});
        }
        parent[i] = i;
    }

    sort(edges.begin(), edges.end(), greater<>());

    vector < vector <int> > ans (n + 1);
    queue <pii> q;

    // 선택한 간선의 수 n-1 개 구하기
    while (q.size() < n - 1)
    {
        int u, v;
        u = edges.back().second.first;
        v = edges.back().second.second;
        edges.pop_back();

        if (getParent(u) != getParent(v))
        {
            unionNodes(u, v);
            q.push({u, v});
        }
    }

    while (!q.empty())
    {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        ans[a].push_back(b);
        ans[b].push_back(a);
    }

    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", ans[i].size());
        sort(ans[i].begin(), ans[i].end());
        for (int j = 0; j < ans[i].size(); ++j)
        {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }

    return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 크루스칼 알고리즘을 활용하여 풀이하였습니다.

A-B 에서 A와 가장 가까운 B만을 남기고, A-B / B-A 를 기록해주면 됩니다.