过题随笔 | 小欧皇（并查集、连通块）| JAVA

import java.util.*;

class Edge {
    int to;
    int nxt;
    Edge(int t,int n) {
        to = t;
        nxt = n;
    }
}
public class Main {
    static void addEdge (int u,int v,int[] head,Edge[] edges,int[] e_cnt) {
        edges[e_cnt[0]] = new Edge(v,head[u]);
        head[u] = e_cnt[0]++;
        edges[e_cnt[0]] = new Edge(u,head[v]);
        head[v] = e_cnt[0]++;
    }
    static int find(int x,int[] pre) {
        if (x != pre[x])
            pre[x] = find(pre[x],pre);
        return pre[x];
    }
    static void join(int x,int y,int[] pre,int[] cnt) {
        int fx = find(x,pre);
        int fy = find(y,pre);
        if (fx != fy) {
            pre[fy] = fx;
            cnt[fx] += cnt[fy];
        }
    }
    static long bonus(long n) {
        if (n < 2) return 0;
        return n*(n-1)/2;
    }
    public static void main(String[] args) {
        //input
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        char[] dot = new char[n+1];
        dot = in.next().toCharArray();

        //construct graph
        int[] head = new int[n+1];
        Edge[] edges = new Edge[2*m+1];
        int[] e_cnt = {0};
        Arrays.fill(head,-1);
        for (int i = 1; i <= m; ++i) {
            int u = in.nextInt();
            int v = in.nextInt();
            addEdge(u,v,head,edges,e_cnt);
        }

        //connected block
        int[] pre = new int[n+1];
        int[] cnt = new int[n+1];
        for (int i = 1;i <= n;++i) {
            pre[i] = i;
            cnt[i] = 1;
        }
        for (int u = 1; u <= n; ++u) {
            if (dot[u-1] == '0') continue;
            for (int i = head[u]; i != -1; i = edges[i].nxt) {
                int v = edges[i].to;
                if (dot[v-1] == '0') continue;
                join(u,v,pre,cnt);
            }
        }
        
        //cal now bonus
        long ans = 0;
        long[] blockBonus = new long[n+1];
        for (int u = 1; u <= n; ++u) {
            if (dot[u-1] == '0') continue;
            if (pre[u] != u) continue;
            int fu = find(u,pre);
            blockBonus[fu] = bonus(cnt[fu]);
            ans += blockBonus[fu];
        }

        //find the max node
        int maxNode = 0;
        long maxBonus = 0;
        for (int u = 1;u <= n;++u) {
            if (dot[u-1] == '1') continue;
            dot[u-1] = '1';

            long theBonus = ans;
            HashSet<Integer> set = new HashSet<>();
            for (int i = head[u]; i != -1; i = edges[i].nxt) {
                int v = edges[i].to;
                if (dot[v-1] == '0') continue;
                set.add(find(v, pre));
            }
            int theCnt = 0;
            for (int obj:set) {
                theCnt += cnt[obj];
                theBonus -= blockBonus[obj];
            }
            theBonus += bonus(theCnt+1);

            dot[u-1] = '0';
            if (theBonus > maxBonus) {
                maxNode = u;
                maxBonus = theBonus;
            }
        }

        System.out.println(maxNode+" "+maxBonus);
    }
}

其实这道题写了一天才A掉。一开始我不知道使用并查集来查连通块，尝试使用BFS查连通块，然后好像原理上可行，但是我想的是建立一个新的图（贸易图），每个连通块都是一个完全图。但是这样空间复杂度太高了，存不下。所以还是换成并查集了。

并查集我也调了一段时间，这里用到了cnt和blocksize分别记录每个连通块的大小和每个连通块的利润。还算是比较典型的题目了，可以当模板题。维护cnt[]的时候我一开始只用cnt[]++，结果一开始的数据比较小都能过，大数据过不了，所以头疼不知道哪错了。后来改成cnt[fx]+=cnt[fy]就可以了。以后遇到这种情况可以详细查看代码里的++是不是有点想的狭隘了。

这种图论的题目，具体算法逻辑其实不难，实现的时候有点麻烦就是了。要有耐心呀