2610번

2610번 - 회의준비

문제를 풀어서 해석하면, 연결 요소의 갯수를 구하고, 플로이드 이용값을 이용하는 문제이다.

연결 요소의 갯수를 구하는 방식은 dfs 나 bfs로 구하는데, 이 문제는 dfs를 통해서 구했다.

그리고 플로이드 알고리즘을 통해 구한 값으로 의사 전달 시간 중 최대값이 최소값이 되는 값을 구할 수 있다.

의사 전달 시간 중 최대값이 최소값이란 말 때문에 나도 처음에 문제를 틀렸고, 

질문 게시판에 보면 그에 따른 많은 질문이 있고, 답변도 있어서 그걸 이해하고 문제를 풀 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
const int INF = 987654321;
int cnt = 0;
void dfs(int c, vector<vector<int>> &v, vector<int> &check)
{
    check[c] = cnt;
 
    for (int i = 0; i < v[c].size(); i++)
    {
        int next = v[c][i];
        if (check[next] == 0)
        {
            check[next] = cnt;
            dfs(next, v, check);
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n + 1);
    vector<vector<int>> D(n + 1, vector<int>(n + 1, INF));
    vector<int> check(n + 1,0);
    while (m--)
    {
        int s, e;
        cin >> s >> e;
        v[s].push_back(e);
        v[e].push_back(s);
        D[s][e] = 1;
        D[e][s] = 1;
    }
 
    for (int i = 1; i <= n; i++)
    {
        D[i][i] = 0;
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
 
    
    for (int i = 1; i <= n; i++)
    {
        if (check[i]==0)
        {
            cnt++;
            dfs(i,v,check);
        }
    }
 
    vector<int> p(cnt + 1);
    vector<int> s(cnt + 1,INF);
 
    for (int i = 1; i <= cnt; i++)
    {
        for (int from = 1; from <= n; from++)
        {
            int maxx = -1;
            if (check[from] != i) continue;
            for (int to = 1; to <= n; to++)
            {
                if (check[to] != i) continue;
                
                if (maxx < D[from][to])
                {
                    maxx = D[from][to];
                }
            }
 
            if (maxx < s[i])
            {
                s[i] = maxx;
                p[i] = from;
            }
        }
    }
 
    sort(p.begin()+1,p.end());
 
    cout << cnt << "\n";
        
    for (int i = 1; i <= cnt; i++)
    {
        cout << p[i] << "\n";
    }
 
 
    return 0;
}