有 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);