2610번: 회의준비

https://www.acmicpc.net/problem/2610


$O(n^3)$

모든 서로 아는 사이에 단위 가중치를 두고 플로이드 알고리즘을 쓰면 임의의 두 사람 사이 의사전달시간을 알 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, d[101][101], maxi[101], res[100], sz, flag[101];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i^j) d[i][j] = 1e9;
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        d[x][y] = d[y][x] = 1;
    }
    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (d[i][j]<1e9&&d[i][j]>maxi[i]) maxi[i] = d[i][j];
    for (int i = 1; i <= n; i++) if (!flag[i]) {
        int t = i;
        for (int j = i; j <= n; j++) if (d[i][j]<1e9) {
            flag[j] = 1;
            if (maxi[t] > maxi[j]) t = j;
        }
        res[sz++] = t;
    }
    sort(res, res + sz);
    printf("%d", sz);
    for (int i = 0; i < sz; i++) printf("\n%d", res[i]);
    return 0;
}