문제 분석

노드들끼리 연결된 하나의 네트워크를 컴포넌트라고 부른다.
밀도는 다음과 같이 정의한다. 컴포넌트에 속한 회선 갯수 / 컴포넌트에 속한 노드수

이 문제의 그래프는 양방향 간선이다. 즉, 무방향으로 줌.

우리가 출력해야 하는 것은 밀도가 가장 큰 네트워크에 속한 노드들에 대한 오름차순 정렬임.
또한, 밀도가 같은 네트워크들이 있다면, 그 중 노드의 갯수가 더 적은 네트워크를 출력한다. 또한, 노드의 수 마저도 같다면, 해당 네트워크 안에 속한 노드값 중 가장 작은것들을 비교해서 더 작은 네트워크를 택한다.

사실, 네트워크를 구분하는 문제들은 꽤 흔해서 이걸 보자마자 그래프 탐색이라는 것은 바로 알아챌 것이다.
하지만, 우리가 이 문제를 풀기 위해 가장 고민할 것은, 양방향 엣지에 대해 어떻게 셀것이냐? 이다. 우선, 가장 간단한 인접행렬은 노드의 수가 10만개라서 만들 수가 없다.

그렇다면, 우리는 bfs의 성질을 이용해야 한다. bfs는 강에 물방울 떨어뜨리는 것과도 같다. 즉, 퍼져 나가면서 최소의 경로로 각 노드에 도달한다는 것이다. 그렇다면, 잘 생각해보면 해당 노드의 차례가 오기 전에 그 부모 노드가 누구였는지를 안다면 중복없이 엣지의 갯수를 모두 셀 수 있다.
현재 노드에서 이웃한 노드들에 대해 방문 여부를 확인하는데 만약 이미 방문했지만 부모 노드가 아니라면 간선 갯수를 세주면 된다. (부모노드인 경우는, 지금 이 노드를 오는 과정에서 부모노드 쪽에서 세었을거기 때문에 또 세면 안된다.)

이런 성질을 이용해서 풀면 된다.

문제 풀이

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		boolean[] isVisited = new boolean[N+1];
		
		ArrayList<Integer>[] graph = new ArrayList[N+1];
		for(int i=1; i<=N;i++) graph[i] = new ArrayList<>();
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a].add(b);
			graph[b].add(a);
		}
		
		ArrayList<Integer> result = new ArrayList();
		int minSize = 10_0000_0000;
		int minNumber = 10_0000_0000;
		double mildo = 0; // double자료형은 d 생략 가능함. float은 f 붙여야함.
		for(int i=1; i<=N; i++) {
			if (isVisited[i]) continue;
			
			LinkedList<Node> q = new LinkedList();
			q.add(new Node(i, 0));
			isVisited[i] = true;
			int nodeSize = 0;
			int edgeSize = 0;
			int curMinNumber = i;
			ArrayList<Integer> curGroup = new ArrayList();
			while(!q.isEmpty()) {
				Node curNode = q.poll();
				nodeSize++;
				curMinNumber = Math.min(curMinNumber, curNode.n);
				curGroup.add(curNode.n);
				for(int neigh: graph[curNode.n]) {
					if (isVisited[neigh]) {
						if (neigh != curNode.parent) edgeSize++;
						continue;
					}
					q.add(new Node(neigh, curNode.n));
					isVisited[neigh] = true;
					edgeSize++;
				}
			}
			
			double curMildo = ((double)edgeSize) / nodeSize;
			if (curMildo > mildo || (curMildo==mildo && nodeSize < minSize) ||
				 (curMildo==mildo && nodeSize==minSize && curMinNumber < minNumber)) {
				mildo = curMildo;
				minSize = nodeSize;
				minNumber = curMinNumber;
				result = curGroup;
			}
		}
		
		Collections.sort(result);
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<result.size(); i++) {
			sb.append(result.get(i)).append(" ");
		}
		
		System.out.println(sb);
	}
}

class Node {
	int n;
	int parent;
	Node(int n, int parent) {
		this.n = n;
		this.parent = parent;
	}
}