朋友圈(后端开发卷)
现在有 105 个用户,编号为 1- 105,现在已知有 m 对关系,每一对关系给你两个数 x 和 y ,代表编号为 x 的用户和编号为 y 的用户是在一个圈子中,例如: A 和 B 在一个圈子中, B 和 C 在一个圈子中,那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。
数据范围:
1≤m≤2×10
6
进阶:空间复杂度 O(n) ,时间复杂度 O(nlogn)
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 256M,其他语言512M
输入描述:
第一行输入一个整数T,接下来有T组测试数据。
对于每一组测试数据:第一行输入1个整数n,代表有n对关系。
接下来n行,每一行输入两个数x和y,代表编号为x和编号为y的用户在同一个圈子里。
1 ≤ T ≤ 10
1 ≤ n ≤ 2*106
1 ≤ x, y ≤ 105
输出描述:
对于每组数据,输出一个答案代表一个圈子内的最多人数
示例1
输入例子:
2
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
输出例子:
4
2
ac代码
// package tencent.tel.sum;
import java.util.Scanner;
class UnionFind {
private int[] parent;
private int[] size;
private int count;
public UnionFind(int n) {
this.parent = new int[n];
this.size = new int[n];
this.count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
public int getMaxUnion(){
int max = 1;
for (int x:size)
max = Math.max(max,x);
return max;
}
}
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while(T-->0){
int n = in.nextInt();
UnionFind u = new UnionFind(100005);
for (int i=0;i<n;i++)
u.union(in.nextInt(), in.nextInt());
System.out.println(u.getMaxUnion());
}
}
}
ac代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while(T-->0){
double A = in.nextDouble();
double B = in.nextDouble();
double C = in.nextDouble();
if (A-2*B*C<=0) {
System.out.println(0);
continue;
}
double result = calculate(A,B,C);
System.out.println(result);
}
}
public static double calculate(double a,double b,double c){
double y1 = a/b+Math.pow((a*a)/(b*b)-(2*a*c)/b,1.0/2);
double y2 = a/b-Math.pow((a*a)/(b*b)-(2*a*c)/b,1.0/2);
double result_1 = jifen(a,b,c,y1);
double result_2 = jifen(a,b,c,y2);
return result_1-result_2;
}
public static double jifen(double a,double b,double c,double y){
return Math.pow(y,2)/(2*b)-(c*y)/b-Math.pow(y,3)/(6*a);
}
}