首页 > 试题广场 >

朋友圈(后端开发卷)

[编程题]朋友圈(后端开发卷)

热度指数：8058 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有 10⁵个用户，编号为 1- 10⁵，现在已知有 m 对关系，每一对关系给你两个数 x 和 y ，代表编号为 x 的用户和编号为 y 的用户是在一个圈子中，例如： A 和 B 在一个圈子中， B 和 C 在一个圈子中，那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。

数据范围： $1 \le m \le 2 \times 10^6 \$
进阶：空间复杂度 $O(n) \$ ，时间复杂度 $O(nlogn) \$

输入描述:

第一行输入一个整数T，接下来有T组测试数据。
对于每一组测试数据：第一行输入1个整数n，代表有n对关系。
接下来n行，每一行输入两个数x和y，代表编号为x和编号为y的用户在同一个圈子里。
1 ≤ T ≤ 10
1 ≤ n ≤ 2*10⁶
1 ≤ x, y ≤ 10⁵

输出描述:

对于每组数据，输出一个答案代表一个圈子内的最多人数

示例1

输入

输出

4
2

算法知识视频讲解

Java

致富

用了并查集模板就是舒服

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];
    }
}

发表于 2022-04-26 16:09:01 回复(0)

Java

牛客839357303号

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

发表于 2021-08-25 00:50:03 回复(0)

Java

Italy炮仗

贴上一个Java版本，利用压缩路径（不然会在10/20处超时）。同时借助size数组同步更新ans避免最后的一次循环。

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]);
    }
}

发表于 2021-07-09 17:20:06 回复(0)