Day_1（并查集朋友圈、字典序排序）

1.并查集

朋友圈：找出最多的一个圈子内有多少用户！

• id[]（表示当前节点的父节点）
• nodeNum[] （表示当前节点为根的那一组节点数量）

import java.util.Scanner;

//并查集
class UnionFind{
    int[] id;   //表示当前结点的父节点
    int[] nodeNum; //表示当前节点为根的那一组的节点数量
    int[] height; //表示当前节点为跟的那一组的节点数高度
    int num; //连通集的数目

    public UnionFind(int n){
        num = n;
        id = new int[n];
        nodeNum = new int[n];
        height = new int[n];

        for(int i=0;i<n;i++){
            id[i] = i;
            nodeNum[i] = 1;
            height[i] = 1;
        }
    }

    public int find(int p){
        while(p != id[p]){
            p = id[p];
        }
        return p;
    }

    public void Union(int p,int q){
        int i = find(p);
        int j = find(q);
        if(i!=j){
            if(height[i]>height[j]){
                id[j] = i;
                nodeNum[i] += nodeNum[j];
            }else if(height[i]<height[j]){
                id[i] = j;
                nodeNum[j] += nodeNum[i];
            }else{
                id[i] = j;
                nodeNum[j] += nodeNum[i];
                height[j]++;
            }
            num--;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int times = sc.nextInt();
        while (times > 0) {
            int n = sc.nextInt();
            UnionFind uf = new UnionFind(10000001);
            for(int i=0;i<n;i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                uf.Union(a,b);
            }
            int max = 1;
            for(int i=0;i<uf.nodeNum.length;i++){
                if(max<uf.nodeNum[i]){
                    max = uf.nodeNum[i];
                }
            }
            System.out.println(max);
            times--;
        }
    }

}

2.按字典序排序的第k小子串

1、找出所有字串

2、字串按照字典序排序

3、找出第k小的字串

import java.util.Scanner;

//字典序第k小的字串
class Heap{
    String[] str;
    public  Heap(int n){
        str = new String[n];
    }
    //比较大小函数
    public boolean CmpStr(String str1,String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        int i =0;
        while(len1>0&&len2>0){
            if(str1.charAt(i)<str2.charAt(i)) return true;
            if(str1.charAt(i)>str2.charAt(i)) return false;
            len1--;
            len2--;
            i++;
        }
        if(len2>0) return true;
        else return false;
    }


    //调整大根堆函数
    public void HeadAdjust(int k,int len){
        str[0] = str[k];
        for(int i=2*k;i<=len;i*=2){
            if(i<len && CmpStr(str[i],str[i+1])) i++;
            if (CmpStr(str[i],str[0])) break;
            else{
                str[k] = str[i];
                k=i;
            }
        }
        str[k] = str[0];
    }

    public void BuildMaxHeap(int len){
        for(int i=len/2;i>0;i--){
            HeadAdjust(i,len);
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = sc.nextInt();
        Heap hs = new Heap(100);
        int k=0;
        int count = 0;
        boolean p=true;

        for(int len = 1; len <= n; len ++) {
            for (int i = 0; i < str.length() - len + 1; i++) {
                String substr = str.substring(i, i + len);
                if(k>0){
                    for(int j=0;j<k;j++){
                        if(substr.equals(hs.str[j+1])) p=false;
                    }
                }

                if(p){
                    if(count<n){
                        k++;
                        count++;
                        hs.str[k] = substr;
                        hs.BuildMaxHeap(k);
                    }else{
                        if(hs.CmpStr(substr,hs.str[1])){
                            hs.str[1] = substr;
                            hs.BuildMaxHeap(k);
                        }
                    }
                }else{
                    p = true;
                }
            }
        }
        System.out.println(hs.str[1]);
    }
}
//aaddsfsddsf
//5
//aadds