사람 n명이 있고, 1번부터 n번까지 번호가 붙어 있다. 친구 관계 m개가 주어지며, 관계 하나는 서로 다른 두 사람 a와 b가 친구라는 뜻이다. 친구 관계는 양쪽으로 성립한다: a가 b의 친구이면 b도 a의 친구이다. 친구의 친구, 그 친구의 친구처럼 친구 관계를 따라 서로 닿을 수 있는 사람들은 같은 무리이다. 친구가 한 명도 없는 사람은 혼자서 무리 하나이다. 같은 쌍의 관계가 여러 번 주어질 수도 있다. 두 줄을 출력하라. 첫 줄에는 무리의 개수를 출력한다. 둘째 줄에는 가장 큰 무리의 사람 수를 출력한다.
6 4 1 2 2 3 4 5 5 4
3 3
3 0
3 1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
사람마다 친구 번호를 모은 인접 목록(adjacency list)을 만들고, 아직 안 본 사람에서 깊이 우선 탐색(DFS)으로 닿는 사람을 모두 표시하면 무리 하나예요.
친구는 양쪽이라 a의 목록에 b, b의 목록에 a를 둘 다 넣어야 해요 — 한쪽만 넣으면 4 3, 3 2처럼 거꾸로 이어진 줄이 여러 무리로 갈라져요.
재귀 DFS는 짧지만 사람들이 한 줄로 이어지면 깊이가 10,000이 돼요: Python은 기본 재귀 한도 1,000에 걸려 RecursionError, 크레이콘도 몇천 단계에서 멈춰요.
그래서 모든 풀이가 스택을 직접 써요: 넣을 때 표시하면 사람마다 한 번만 들어가고, 꺼낼 때 표시하면 고리(1-2, 2-3, 3-1)에서 같은 사람이 여러 번 들어가 크기를 꺼낸 횟수로 세면 부풀어요.
인접 목록 만들기: Python [[] for _ in range(n + 1)]([[]] * (n + 1)은 모든 칸이 같은 목록이에요), JavaScript·TypeScript Array.from({ length: n + 1 }, () => []), Java List<List<Integer>>(int는 Integer로 싸서 넣어요), C# List<int>[](칸마다 new List<int>()), C++ std::vector<std::vector<int>>, C는 크기가 정해지지 않은 목록이 없어서 head·next·to 배열로 사람마다 이웃을 사슬처럼 이어요.
크레이콘은 목록 안에 목록을 넣고(friends.넣기([])) 스택은 목록 끝을 맨 위로 써요(stack[stack.개수 - 1], 자리빼기(stack.개수 - 1)).
번호가 1부터라 칸을 n + 1개 만들고 0번은 비워 둬요 — 크레이콘만은 목록이 10,000칸까지라 10,001칸을 못 만들어서, 번호에서 1을 빼 0번부터 담아요.
친구가 없는 사람도 바깥 반복이 1번부터 n번까지 모두 돌아서 무리로 세어져요.
import sys data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) # 인접 목록(adjacency list): friends[p] = p와 친구인 사람들. 친구는 서로 친구라 양쪽에 넣는다friends = [[] for _ in range(n + 1)]for i in range(m): a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i]) friends[a].append(b) friends[b].append(a) seen = [False] * (n + 1)groups = 0largest = 0for start in range(1, n + 1): if seen[start]: continue # 깊이 우선 탐색(DFS)을 스택으로 — 재귀로 쓰면 줄처럼 이어진 무리에서 깊이가 10,000이 된다 groups += 1 seen[start] = True stack = [start] size = 0 while stack: p = stack.pop() size += 1 for q in friends[p]: if not seen[q]: seen[q] = True stack.append(q) largest = max(largest, size)print(groups)print(largest)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 인접 목록(adjacency list): friends[p] = p와 친구인 사람들. 친구는 서로 친구라 양쪽에 넣는다const friends = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; friends[a].push(b); friends[b].push(a);} const seen = new Array(n + 1).fill(false);let groups = 0, largest = 0;for (let start = 1; start <= n; start++) { if (seen[start]) continue; // 깊이 우선 탐색(DFS)을 스택으로 — 재귀로 쓰면 줄처럼 이어진 무리에서 깊이가 10,000이 된다 groups++; seen[start] = true; const stack = [start]; let size = 0; while (stack.length > 0) { const p = stack.pop(); size++; for (const q of friends[p]) { if (!seen[q]) { seen[q] = true; stack.push(q); } } } largest = Math.max(largest, size);}console.log(groups);console.log(largest);import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 인접 목록(adjacency list): friends[p] = p와 친구인 사람들. 친구는 서로 친구라 양쪽에 넣는다const friends: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; friends[a].push(b); friends[b].push(a);} const seen: boolean[] = new Array<boolean>(n + 1).fill(false);let groups = 0, largest = 0;for (let start = 1; start <= n; start++) { if (seen[start]) continue; // 깊이 우선 탐색(DFS)을 스택으로 — 재귀로 쓰면 줄처럼 이어진 무리에서 깊이가 10,000이 된다 groups++; seen[start] = true; const stack: number[] = [start]; let size = 0; while (stack.length > 0) { const p = stack.pop()!; // 비어 있지 않음을 위에서 확인했다 size++; for (const q of friends[p]) { if (!seen[q]) { seen[q] = true; stack.push(q); } } } largest = Math.max(largest, size);}console.log(groups);console.log(largest);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); // 인접 목록(adjacency list): friends.get(p) = p와 친구인 사람들. 친구는 서로 친구라 양쪽에 넣는다 List<List<Integer>> friends = new ArrayList<>(); for (int p = 0; p <= n; p++) friends.add(new ArrayList<>()); for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); friends.get(a).add(b); friends.get(b).add(a); } boolean[] seen = new boolean[n + 1]; int groups = 0, largest = 0; for (int start = 1; start <= n; start++) { if (seen[start]) continue; // 깊이 우선 탐색(DFS)을 스택으로 — 재귀로 쓰면 줄처럼 이어진 무리에서 깊이가 10,000이 된다 groups++; seen[start] = true; ArrayDeque<Integer> stack = new ArrayDeque<>(); stack.push(start); int size = 0; while (!stack.isEmpty()) { int p = stack.pop(); size++; for (int q : friends.get(p)) { if (!seen[q]) { seen[q] = true; stack.push(q); } } } largest = Math.max(largest, size); } System.out.println(groups); System.out.println(largest); }}using System;using System.Collections.Generic; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int m = int.Parse(first[1]); // 인접 목록(adjacency list): friends[p] = p와 친구인 사람들. 친구는 서로 친구라 양쪽에 넣는다 var friends = new List<int>[n + 1]; for (int p = 0; p <= n; p++) friends[p] = new List<int>(); for (int i = 0; i < m; i++) { string[] pair = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(pair[0]); int b = int.Parse(pair[1]); friends[a].Add(b); friends[b].Add(a); } var seen = new bool[n + 1]; int groups = 0, largest = 0; for (int start = 1; start <= n; start++) { if (seen[start]) continue; // 깊이 우선 탐색(DFS)을 스택으로 — 재귀로 쓰면 줄처럼 이어진 무리에서 깊이가 10,000이 된다 groups++; seen[start] = true; var stack = new Stack<int>(); stack.Push(start); int size = 0; while (stack.Count > 0) { int p = stack.Pop(); size++; foreach (int q in friends[p]) { if (!seen[q]) { seen[q] = true; stack.Push(q); } } } largest = Math.Max(largest, size); } Console.WriteLine(groups); Console.WriteLine(largest); }}#include <algorithm>#include <iostream>#include <stack>#include <vector> int main() { int n, m; std::cin >> n >> m; // 인접 목록(adjacency list): friends[p] = p와 친구인 사람들. 친구는 서로 친구라 양쪽에 넣는다 std::vector<std::vector<int>> friends(n + 1); for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; friends[a].push_back(b); friends[b].push_back(a); } std::vector<bool> seen(n + 1, false); int groups = 0, largest = 0; for (int start = 1; start <= n; start++) { if (seen[start]) continue; // 깊이 우선 탐색(DFS)을 스택으로 — 재귀로 쓰면 줄처럼 이어진 무리에서 깊이가 10,000이 된다 groups++; seen[start] = true; std::stack<int> stack; stack.push(start); int size = 0; while (!stack.empty()) { int p = stack.top(); stack.pop(); size++; for (int q : friends[p]) { if (!seen[q]) { seen[q] = true; stack.push(q); } } } largest = std::max(largest, size); } std::cout << groups << "\n" << largest << "\n";}#include <stdbool.h>#include <stdio.h> #define MAXN 10001#define MAXE 20000 /* 친구 한 쌍은 양쪽으로 두 번 들어간다 */ /* 인접 목록을 배열로: head[p]는 p의 첫 이웃 칸, next[e]는 같은 사람의 다음 이웃 칸(-1이면 끝) */static int head[MAXN], next[MAXE], to[MAXE];static int edges = 0;static bool seen[MAXN];static int stack[MAXN]; static void add_friend(int a, int b) { to[edges] = b; next[edges] = head[a]; head[a] = edges++;} int main(void) { int n, m; scanf("%d %d", &n, &m); for (int p = 1; p <= n; p++) head[p] = -1; for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); add_friend(a, b); /* 친구는 서로 친구라 양쪽에 넣는다 */ add_friend(b, a); } int groups = 0, largest = 0; for (int start = 1; start <= n; start++) { if (seen[start]) continue; /* 깊이 우선 탐색(DFS)을 스택으로 — 사람마다 한 번만 넣으니 n칸이면 된다 */ groups++; seen[start] = true; int top = 0, size = 0; stack[top++] = start; while (top > 0) { int p = stack[--top]; size++; for (int e = head[p]; e != -1; e = next[e]) { int q = to[e]; if (!seen[q]) { seen[q] = true; stack[top++] = q; } } } if (size > largest) largest = size; } printf("%d\n%d\n", groups, largest); return 0;}첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1]; // 인접 목록: friends[p - 1] = p번과 친구인 사람들. 목록은 10,000칸까지라 n + 1칸 대신 번호에서 1을 빼서 둔다friends = [];반복 (p = 0; p < n; p++){ friends.넣기([]);}반복 (i = 0; i < m; i++){ 쌍 = 콘솔.수들읽기(); a = 쌍[0] - 1; b = 쌍[1] - 1; friends[a].넣기(b); // 친구는 서로 친구라 양쪽에 넣는다 friends[b].넣기(a);} seen = 새목록(n, 거짓);groups = 0;largest = 0;반복 (start = 0; start < n; start++){ 만약 (!seen[start]) { // 깊이 우선 탐색(DFS)을 스택으로 — 크레이콘 재귀는 몇천 단계에서 멈춘다. 맨 위는 목록 끝 groups += 1; seen[start] = 참; stack = [start]; size = 0; 동안 (stack.개수 > 0) { p = stack[stack.개수 - 1]; stack.자리빼기(stack.개수 - 1); size += 1; 각각 (q 에서 friends[p]) { 만약 (!seen[q]) { seen[q] = 참; stack.넣기(q); } } } largest = 수학.큰수(largest, size); }}콘솔.쓰기(groups);콘솔.쓰기(largest);