통신망 분석

문제

풀이

dfs나 bfs로 풀 수 있는 문제였다. 사실 이 문제는 못 풀고 다음날 올라온 풀이를 보면서 다시 해결했다.
조건이 조금 까다로웠는데, 탐색 과정에서 각 노드별로 컴포넌트 넘버를 지정해주고 나중에 가장 밀도가 높은 컴포넌트만 출력해주면 됐다.

탐색도 탐색이지만 이것저것 부가적인 조건이 붙어서 푸는데 애를 먹었다.

이번에도 bfs와 마찬가지로 visit배열을 이용해서 방문기록을 남겼다. 한번이라도 방문했으면 해당 노드는 접근하지 않도록 했다.

dfs를 사용해서 풀었는데, 풀이 과정은 이렇다.

1. 메인 함수에서 전체노드를 반복하며 아직 방문하지 않은 노드라면 dfs를 실행시킨다.

2. dfs함수 내에서 컴포넌트 넘버, 해당 컴포넌트의 엣지 크기, 노드 크기를 저장한 뒤에 노드와 연결된 다음 노드를 dfs에 넘긴다.

3. 이렇게 재귀를 돌다보면 어느순간 연결이 끊기게 되는데 그 시점이 dfs함수가 종료되는 시점이자 컴포넌트 하나에 대한 연산이 종료되는 시점이다.

4. 메인 함수에서 모든 노드에 대해 dfs를 실행시키고 나면 컴포넌트의 엣지와 노드 수가 기록되는데, 이 정보를 바탕으로 밀집도가 가장 높은 컴포넌트를 구한다.

5. 해당 컴포넌트에 해당하는 노드를 출력한다. 단, 오름차순으로!

이 과정을 수행하는 코드는 다음과 같다.

#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

const int MAX = 100007;
vector<int> G[MAX];
ll compNum[MAX], edge[MAX], node[MAX];
bool visited[MAX];

void DFS(int cur, int num) {
    compNum[cur] = num;
    edge[num] += G[cur].size();
    node[num]++;
    for (int next : G[cur]) {
        if (visited[next]) continue;
        visited[next] = 1;
        DFS(next, num);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int num = 0;
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        visited[i] = 1;
        DFS(i, ++num);
        edge[num] /= 2;
    }

    int ans = 1;
    for (int i = 2; i <= num; ++i) {
        if (edge[i] * node[ans] > edge[ans] * node[i]) ans = i;
        else if (edge[i] * node[ans] == edge[ans] * node[i]) {
            if (node[i] < node[ans]) ans = i;
        }
    }

    for (int i = 1; i <= N; ++i) {
        if (compNum[i] == ans) cout << i << ' ';
    }
    return 0;
}