There are n people, numbered 1 to n.
m friendships are given; each one means that two different people a and b are friends.
Friendship goes both ways: if a is b's friend, b is also a's friend.
People who can reach each other by following friendships, like a friend of a friend of a friend, are in the same group.
A person with no friends forms a group alone.
The same pair may be given more than once.
Print two lines.
The first line is the number of groups.
The second line is the number of people in the largest group.
Input
The first line has n and m; each of the next m lines has a and b separated by a space. 1 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 1 ≤ a, b ≤ n, a ≠ b
Output
First line: the number of groups; second line: the size of the largest group
Example 1 · stdin
6 4
1 2
2 3
4 5
5 4
stdout
3
3
Example 2 · stdin
3 0
stdout
3
1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Build an adjacency list holding each person's friends, then from a person not yet seen, mark everyone reachable with depth-first search (DFS): that is one group. Friendship goes both ways, so put b in a's list and a in b's list — with only one side, a chain given backwards like 4 3, 3 2 splits into several groups. Recursive DFS is short, but when people form one long line the depth reaches 10,000: Python hits its default recursion limit of 1,000 and raises RecursionError, and Craykon also stops at a few thousand levels. So every solution uses an explicit stack: marking on push puts each person in only once, while marking on pop lets a cycle (1-2, 2-3, 3-1) push the same person several times, so counting pops inflates the size. Building the adjacency list: Python [[] for _ in range(n + 1)] ([[]] * (n + 1) makes every cell the same list), JavaScript/TypeScript Array.from({ length: n + 1 }, () => []), Java List<List<Integer>> (an int is boxed as Integer), C# List<int>[] (a new List<int>() in each cell), C++ std::vector<std::vector<int>>, and C, which has no growable list, chains each person's neighbours through head, next and to arrays. Craykon puts lists inside a list (friends.Add([])) and uses the end of a list as the stack top (stack[stack.Count - 1], RemoveAt(stack.Count - 1)). Numbers start at 1, so make n + 1 cells and leave cell 0 empty — except in Craykon, whose lists stop at 10,000 items, so 10,001 cells do not fit and it subtracts 1 from each number to start at 0. People with no friends are still counted, because the outer loop visits every person from 1 to n.
Pythonmain.py · 33 lines
import sysdata = 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)
JavaScriptmain.js · 34 lines
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);
TypeScriptmain.ts · 36 lines
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);
JavaMain.java · 52 lines
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); }}
C#Main.cs · 53 lines
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); }}
C++main.cpp · 43 lines
#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";}
Cmain.c · 53 lines
#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;}
Craykonmain.cray · 50 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];// 인접 목록: friends[p - 1] = p번과 친구인 사람들. 목록은 10,000칸까지라 n + 1칸 대신 번호에서 1을 빼서 둔다friends = [];for (p = 0; p < n; p++){ friends.Add([]);}for (i = 0; i < m; i++){ 쌍 = Console.ReadNumbers(); a = 쌍[0] - 1; b = 쌍[1] - 1; friends[a].Add(b); // 친구는 서로 친구라 양쪽에 넣는다 friends[b].Add(a);}seen = NewList(n, false);groups = 0;largest = 0;for (start = 0; start < n; start++){ if (!seen[start]) { // 깊이 우선 탐색(DFS)을 스택으로 — 크레이콘 재귀는 몇천 단계에서 멈춘다. 맨 위는 목록 끝 groups += 1; seen[start] = true; stack = [start]; size = 0; while (stack.Count > 0) { p = stack[stack.Count - 1]; stack.RemoveAt(stack.Count - 1); size += 1; foreach (q in friends[p]) { if (!seen[q]) { seen[q] = true; stack.Add(q); } } } largest = Mathf.Max(largest, size); }}Console.WriteLine(groups);Console.WriteLine(largest);