现在有 105 个用户,编号为 1- 105,现在已知有 m 对关系,每一对关系给你两个数 x 和 y ,代表编号为 x 的用户和编号为 y 的用户是在一个圈子中,例如: A 和 B 在一个圈子中, B 和 C 在一个圈子中,那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。
数据范围:
进阶:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
第一行输入一个整数T,接下来有T组测试数据。
对于每一组测试数据:第一行输入1个整数n,代表有n对关系。接下来n行,每一行输入两个数x和y,代表编号为x和编号为y的用户在同一个圈子里。1 ≤ T ≤ 101 ≤ n ≤ 2*1061 ≤ x, y ≤ 105
对于每组数据,输出一个答案代表一个圈子内的最多人数
2 4 1 2 3 4 5 6 1 6 4 1 2 3 4 5 6 7 8
4 2
用了并查集模板就是舒服
import java.util.*; public class Main{ static int N = 100010; // 习惯了超出10个 static int[] p = new int[N + 1]; // 每个用户的父节点 static int[] size = new int[N + 1]; // 只保证根节点的数量正确有效即可 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int k = 0; k < T; k++) { // 每次都初始化所有用户(因为题目给了 T 组测试数据) for (int i = 1; i <= N; i++) { p[i] = i; size[i] = 1; } int n = sc.nextInt(); // n对关系 for (int i = 0; i < n; i++) { int x = sc.nextInt(); int y = sc.nextInt(); if(find(x) == find(y)) continue; // 不能重复挂 // x挂到y上 之前,先统计x、y两个集合人数,再把x挂到y size[find(y)] += size[find(x)]; //先统计两个集合点数 p[find(x)] = find(y); // 把x挂到y的根节点上 } // 统计那个最大朋友圈的用户数 int res = 0; for (int i : size) { res = Math.max(res, i); } System.out.println(res); } } // 找出x的根节点(带路径压缩) public static int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } }
import java.util.Scanner; import java.Lang.String; class Solution { public String replaceSpace(String s) { StringBuilder string = new StringBuilder(); for (int i = 0; i < s.length(); i++){ char c = s.charAt(i); if (c == ' '){ string.append("%20"); } else { string.append(c); } } return string.toString(); } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String input = in.nextLine(); Solution process = new Solution(); String output = process.replaceSpace(input); System.out.println(output); } }
import java.util.*; public class Main { static final int N = (int)Math.pow(10, 7); static int fa[] = new int[N+1]; static int size[] = new int[N+1]; static int ans = 1; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); while (T-- > 0) { int n = scan.nextInt(); init(); for (int i = 0; i < n; i++) { int x = scan.nextInt(); int y = scan.nextInt(); merge(x, y); } System.out.println(ans); } } public static void init() { ans = 1; for (int i = 1; i <= N; i++) { fa[i] = i; size[i] = 1; } } public static int find(int x) { if (fa[x] == x) { return x; } else { fa[x] = find(fa[x]); //压缩路径 return fa[x]; } } public static void merge(int i, int j) { int x = find(i), y = find(j); if (x == y) return; //由于我们使用size记录x,y树的大小,若已经互相包含彼此,不可重复加 fa[y] = x; size[x] += size[y]; ans = Math.max(ans, size[x]); } }