小欧皇

java -时间太慢版，工程项目干多了是这样的，都得新建个类：

import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        //城市类
        class City {
            private Integer id;
            private List<City> connects = new ArrayList<>();//道路

            private boolean zhanling = false; //是否占领
            Set<City> citySet;
            public void setId(Integer id) {
                this.id = id;
            }
            public Integer getId() {
                return id;
            }
            public List<City> getConnects() {
                return connects;
            }
            public boolean isZhanling() {
                return zhanling;
            }
            public void setZhanling(boolean zhanling) {
                this.zhanling = zhanling;
            }
            public String toString() {
                return id.toString();
            }

        }

        Scanner in = new Scanner(System.in);

        Map<Integer, City> citys = new HashMap<>();
        int n = in.nextInt();
        int m = in.nextInt();
        String chuan = in.next();
        String[] chuans = chuan.split("");

        // 解析数据
        {
            while (in.hasNextInt()) { // 注意 while 处理多个 case
                Integer a = in.nextInt();
                Integer b = in.nextInt();
                City city1 = citys.get(a);
                if (city1 == null) {
                    city1 = new City();
                    city1.setId(a);
                    citys.put(a, city1);
                }
                City city2 = citys.get(b);
                if (city2 == null) {
                    city2 = new City();
                    city2.setId(b);
                    citys.put(b, city2);
                }

                city1.getConnects().add(city2);
                city2.getConnects().add(city1);

            }

            //占领赋值
            for (int i = 0; i < chuans.length; i++) {
                String c = chuans[i];
                if (c.equals("1")) {
                    City city = citys.get(i + 1);
                    if (city == null) {
                        city = new City();
                        city.setId(i + 1);
                        citys.put(i + 1, city);
                    }
                    city.setZhanling(true);
                }
            }
        }
        //统计城市连通区间(已占领)，并计算目前总收益
        Set<Set<City>> citySets = new HashSet<>();
        {
            Set<City> added = new HashSet<>();
            for (City city : citys.values()) {

                if (added.contains(city) || !city.isZhanling()) {
                    continue;
                }

                Set<City> cArea = new HashSet<>();//该区域所有城市
                Set<City> newAdd = new HashSet<>();//本次循环新增
                Set<City> lastAdd = new HashSet<>();
                newAdd.add(city);
                cArea.add(city);

                while (!newAdd.isEmpty()) {
                    lastAdd = newAdd;
                    newAdd = new HashSet<>();

                    for (City c : lastAdd) {
                        List<City> connects = c.getConnects();
                        for (City cs : connects) {
                            if (cs.isZhanling() && !cArea.contains(cs)) {
                                newAdd.add(cs);
                            }
                        }
                    }
                    cArea.addAll(newAdd);

                }
                added.addAll(cArea);
                citySets.add(cArea);
            }
        }

        int ec_now = 0;//原始总收益
        for (Set<City> citySet : citySets) {
            int size = citySet.size();
            ec_now += size * (size - 1) / 2;
            for (City c : citySet) {
                c.citySet = citySet;
            }
        }

        //计算新增收益
        int max = 0;
        City maxCity = null;
        for (City city : citys.values()) {
            if (!city.isZhanling()) {
                int count_new = 1;//自身
                int shouyi_origin = 0;//局部原始收益
                Set<Set<City>> counts = new
                HashSet<>();//连的城市的所在原始连通区间
                List<City> connects = city.getConnects();
                for (City city0 : connects) {
                    if (city0.isZhanling()) {
                        counts.add(city0.citySet);
                    }
                }

                for (Set<City> set : counts) {
                    int size = set.size();
                    count_new += size;
                    shouyi_origin += size * (size - 1) / 2;
                }

                int shouyi_new = count_new * (count_new - 1) / 2;//占领city后局部总收益
                int temp = shouyi_new - shouyi_origin;//新增收益

                if (temp > max || (temp == max && (maxCity == null ||
                                                   city.getId() < maxCity.getId()))) {
                    maxCity = city;
                    max = temp;
                }

            }
        }


        System.out.println(maxCity.id + " " + (max + ec_now));
    }


}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int[] fa, size;

    static int find(int x) {
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }

    static void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (size[fx] < size[fy]) {
            size[fy] += size[fx];
            fa[fx] = fy;
        } else {
            size[fx] += size[fy];
            fa[fy] = fx;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        sc.nextLine();
        fa = new int[n + 1];
        size = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            size[i] = 1;
        }

        String occ = sc.nextLine();
        char[] chs = occ.toCharArray();
        List<Integer>[] G = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) G[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            G[u].add(v);
            G[v].add(u);
            if (chs[u - 1] == '1' && chs[v - 1] == '1') union(v, u);
        }

        long ans = 0;
        boolean[] used = new boolean[n + 1];
        for (int u = 1; u <= n; u++) {
            int f = find(u);
            if (used[f]) continue;
            used[f] = true;
            ans += (long) size[f] * (size[f] - 1) / 2;
        }
        // System.out.println(ans);

        long maxProfit = 0;
        int idx = -1;
        Arrays.fill(used, false);
        for (int u = 1; u <= n; u++) {
            if (chs[u - 1] == '0') {
                long curProfit = 0, pref = 1;
                for (int v : G[u]) {
                    int f = find(v);
                    if (chs[v - 1] == '0' || used[f]) continue;
                    used[f] = true;
                    curProfit += pref * size[f];
                    pref += size[f];
                }
                for (int v : G[u]) {
                    int f = find(v);
                    if (chs[v - 1] == '0' || !used[f]) continue;
                    used[f] = false;
                }
                if (curProfit > maxProfit) {
                    maxProfit = curProfit;
                    idx = u;
                }
            }
        }
        System.out.println(idx + " " + (ans + maxProfit));
    }
}