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()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
人ごとに友だちの番号を集めた隣接リスト（adjacency list）を作り、まだ見ていない人から深さ優先探索（DFS）で行き着ける人をすべて印をつければ輪一つです。
友だちは両方向なので、a のリストに b、b のリストに a を両方入れる必要があります — 片方だけだと 4 3、3 2 のように逆向きに与えられた列がいくつもの輪に割れます。
再帰 DFS は短いのですが、人が一列につながると深さが 10,000 になります：Python は既定の再帰上限 1,000 に引っかかって RecursionError、Craykon も数千段で止まります。
そこで、すべての解答がスタックを自分で使います：入れるときに印をつければ一人一回だけ入り、取り出すときに印をつけると閉路（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 の配列で人ごとに隣を鎖のようにつなぎます。
Craykon はリストの中にリストを入れ（friends.追加([])）、スタックはリストの末尾を一番上として使います（stack[stack.個数 - 1]、位置で取り除く(stack.個数 - 1)）。
番号が 1 からなのでマスを n + 1 個作り、0 番は空けておきます — Craykon だけはリストが 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);