2、并查集&合并集合&

AcWing 836. 合并集合

AcWing 837. 连通块中点的数量

AcWing 240. 食物链

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.dandiaozhan();

    }

    int N = 100010;
    Stack<Integer> stack = new Stack();

    //维护单调栈
    void dandiaozhan() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            if (!stack.empty()) {
                if (stack.peek() >= nums[i]) {
                    while (!stack.empty() && stack.peek() >= nums[i]) {
                        stack.pop();
                    }
                    if (!stack.empty()) System.out.print(stack.peek() + " ");
                    else System.out.print(-1+" ");
                    stack.push(nums[i]);
                } else {
                    System.out.print(stack.peek() + " ");
                    stack.push(nums[i]);
                }
            } else {
                System.out.print(-1 + " ");
                stack.push(nums[i]);
            }
        }
    }
}

837. 连通块中点的数量

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.HebingJihe();
    }
    int N=100010;
    int pp[]=new int[N];
    int size[]=new int[N];
    int find(int x){//找到祖宗结点编号
        if(pp[x]!=x) pp[x]=find(pp[x]);
        return pp[x];
    }
    void HebingJihe(){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        for (int i = 1; i <=n; i++) {
            pp[i]=i;
            size[i]=1;
        }
        for (int i = 0; i < m; i++) {
            String d= scanner.next();
            int a= scanner.nextInt();
            if(d.equals("C")){
                int b= scanner.nextInt();
                if(find(a)==find(b)) continue;
                size[find(b)]+=size[find(a)];
                pp[find(a)]=find(b);
            }
            if(d.equals("Q1")){
                int b= scanner.nextInt();
                if(find(a)==find(b)){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
            if(d.equals("Q2")){
                System.out.println(size[find(a)]);
            }
        }
    }
}

240. 食物链

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.Shiwulian();
    }

    int N = 50010;
    int p[] = new int[N];
    int d[] = new int[N];

    int find(int x) {//找到祖宗结点编号
        if (p[x] != x) {
            int t = find(p[x]);
            d[x] += d[p[x]];//d[x]本来都是到前一个的距离
            p[x] = t;
        }
        return p[x];
    }

    void Shiwulian() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            int op = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            if (x > n || y > n) res++;
            else {
                int fx = find(x), fy = find(y);
                //1表示x和y是同类
                if (op == 1) {
                    if (fx == fy) {
                        if ((d[x] - d[y]) % 3 != 0)
                            res++;
                    } else {
                        p[fx] = fy;
                        d[fx] = d[y] - d[x];
                    }
                }
                //2表示x吃y
                if (op == 2) {
                    if (fx == fy) {
                        if ((d[x] - d[y]) % 3 == 0)
                            res++;
                    } else {
                        p[fx] = fy;
                        d[fx] = d[y] - d[x] + 1;
                    }
                }
            }
        }
        System.out.println(res);
    }
}