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());
ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
for(int i =0; i <= N; i++){
arr.add(new ArrayList<Integer>());
}
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr.get(a).add(b);
arr.get(b).add(a);
}
Queue<Integer> q = new LinkedList<>();
boolean []visited = new boolean[N+1];
ArrayList<Node> ans = new ArrayList<>();
for(int i = 0; i < N; i++){
Double edge = 0.0;
Node nd = new Node();
if(arr.get(i).size() > 0 && !visited[i]){
visited[i] = true;
nd.nodeNum.add(i);
for(int j = 0; j < arr.get(i).size(); j++){
q.add(arr.get(i).get(j));
}
while (!q.isEmpty()){
int nextNode = q.poll();
edge++;
if(!visited[nextNode]){
visited[nextNode] = true;
nd.nodeNum.add(nextNode);
for(int j = 0; j < arr.get(nextNode).size(); j++){
q.add(arr.get(nextNode).get(j));
}
}
}
nd.ans = edge / nd.nodeNum.size();
ans.add(nd);
}
}
for(int i = 0; i < ans.size(); i++)
Collections.sort(ans.get(i).nodeNum);
Collections.sort(ans, Node.customComparator);
System.out.println(ans.get(0).ans);
for(int i = 0; i <ans.get(0).nodeNum.size(); i++)
System.out.print(ans.get(0).nodeNum.get(i) + " ");
}
}
class Node{
ArrayList<Integer> nodeNum = new ArrayList<>();
Double ans;
public static Comparator<Node> customComparator = new Comparator<Node>() {
@Override
public int compare(Node node1, Node node2) {
// 1. ans가 가장 높은 것
int ansComparison = Double.compare(node2.ans, node1.ans);
if (ansComparison != 0) {
return ansComparison;
}
// 2. ans가 같을 때 nodeNum의 인자갯수가 적은 것
int numCountComparison = Integer.compare(node1.nodeNum.size(), node2.nodeNum.size());
if (numCountComparison != 0) {
return numCountComparison;
}
// 3. 2까지 같을 때는 nodeNum의 인자 중 가장 작은 인자가 있는 Node
for (int i = 0; i < node1.nodeNum.size(); i++) {
int numComparison = Integer.compare(node1.nodeNum.get(i), node2.nodeNum.get(i));
if (numComparison != 0) {
return numComparison;
}
}
return 0; // 모든 비교 기준이 같을 경우
}
};
}
쉽게 말하면 노드와 간선 수를 둘 다 구하면 된다.
근데 약간 꼼수 아닌 꼼수가 있다면, 실제는 양방향 간선으로 양 노드 간 간선 수를 하나로 세야 하지만,
그냥 각각 노드에서 간선의 수를 카운트 했기 때문에 2개로 치고 풀었다.
그래서 실제 밀도를 구하면 예시와는 다르지만 답은 맞는다.
그리고 밀도가 같을 때가 참 지저분한데, 그건 우리 형 gpt의 도움을 받아서 comparator의 compare 메소드를 오버라이드 해서 구현했다.
제시한 정답에서는 간선의 개수를 따로 세었는데. 난 그냥 탐색할 때 카운트 했다.
'알고리즘-문제' 카테고리의 다른 글
| 구름톤 챌린지 4주 차 문제 18 학습 일기 (0) | 2024.02.18 |
|---|---|
| 구름톤 챌린지 3주 차 문제 13 학습 일기 (0) | 2024.02.18 |
| 백준 1436 영화감독 숌 (0) | 2024.02.18 |
| 백준 1753 최단경로 (0) | 2024.02.18 |
| 백준 1074 Z C언어 (0) | 2024.02.18 |
