문제

바로 접근법을 떠올린 기분 좋은 문제이다!

문제 링크

문제 접근

  • 일단 서로 알고 있는 사람은 같은 위원회에 속해야 한다는 말을 보자마자 union-find로 접근해야지 하고 생각했다.
  • 그렇다면 각 set마다 대표를 어떻게 찾아야할까?

위원회 대표 찾기

  • 대표는 같은 set 안에 있는 원소 중에 제일 먼 거리에 있는 원소와의 거리가 제일 짧은(?) 애를 찾는 것이다.(말이 어렵다ㅎㅎ)
  • 즉 위원회 대표를 찾기 위해서는 set 안에 있는 하나의 노드에서 set 안에 있는 모든 노드까지의 거리를 구해야 한다.
  • 나는 이를 구하기 위해서 플로이드 와샬 알고리즘을 사용했다.
  • 어차피 같은 set 안에 있는 애들의 거리는 업데이트 되지 않을 것이기 때문에 a와 b 사이 거리인 arr[a][b]가 INF가 아니라면 a와 b는 같은 set에 있다는 것을 의미한다.
  • 이를 각 set의 대표는 각 set의 최고 조상 위치에 저장한다.(find함수를 이용해서!)
  • 그리고 대표(rep)에 값이 있는 애들을 가져와서 sort해서 출력한다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 100000
int n, m, v1, v2, arr[101][101], par[101], rep[101], rev[101];
int find(int x){
    if(par[x] == x)return x;
    return par[x] = find(par[x]);
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)arr[i][j] = 100000;
        rev[i] = INF, rep[i] = -1, par[i] = i, arr[i][i] = 0;

    }
    while(m--){
        scanf("%d %d", &v1, &v2);
        arr[v1][v2] = arr[v2][v1] = 1;
        int p1 = find(v1), p2 = find(v2);
        if(p1 != p2)par[p1] = p2;
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][k] + arr[k][j] < arr[i][j])arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int p1 = find(i), max = -1;
        for(int j = 1; j <= n; j++){
            if(arr[i][j] == INF)continue;
            if(max < arr[i][j])max = arr[i][j];
        }
        if(rev[p1] > max)rev[p1] = max, rep[p1] = i;
    }
    vector<int> ans;
    for(int i = 1; i <= n; i++){
        if(rep[i] != -1) ans.push_back(rep[i]);
    }
    sort(ans.begin(), ans.end());
    printf("%lu\n", ans.size());
    for(int i = 0; i < ans.size(); i++)printf("%d\n", ans[i]);
}