题意

小欧正在扮演一个中世纪的皇帝。地图上有n个城市，其中有m条道路，每条道路连接了两个城市。

小欧占领了其中一些城市。如果两个城市可以通过若干条道路互相到达，且这些道路经过的城市都是小欧占领的，那么这两个城市之间就可以通过经商获得收益1。请注意，每两个城市之间的收益只会被计算一次。

现在，小欧准备占领一个未被占领的城市，使得总收益最大化。你能帮帮她吗？

思路

如果一个联通块的大小为x，那么可以获得的收益是C[x][2] ，也就是从这个联通块里选2个点的方案数，x*(x-1)/2

具体思路：

1. 用并查集找出所有的联通块和联通块大小
2. 维护当前能够得到的收益
3. 枚举所有未占领的城市，看把这个城市占领后能得到的收益。具体的计算过程是维护新联通块的大小，枚举所有和这个点相邻的点，减去这个点所在的联通块的贡献，再将这个联通块的大小加入到新联通块的大小里。这里要注意去重，每个联通块只需计算一次，可以用哈希表标识下每个root节点

Go代码

package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	var s string
	fmt.Scan(&s)
	s = " " + s //下标从1开始
	grid := make([][]int, n+1)
	root := make([]int, n+1) //祖先节点
	siz := make([]int, n+1)  //联通块大小
	vis := make([]bool, n+1)
	for i := 1; i <= n; i++ {
		grid[i] = make([]int, 0)
		root[i] = i
		siz[i] = 1
		vis[i] = false
	}
	var find func(int) int
	find = func(x int) int {
		if x != root[x] {
			root[x] = find(root[x])
		}
		return root[x]
	}
	merge := func(x, y int) {
		fx, fy := find(x), find(y)
		if fx == fy {
			return
		}
		root[fx] = fy
		siz[fy] += siz[fx]
	}
	for i := 1; i <= m; i++ {
		var u, v int
		fmt.Scan(&u, &v)
		if s[u] == '1' && s[v] == '1' {
			merge(u, v)
		}
		grid[u] = append(grid[u], v)
		grid[v] = append(grid[v], u)
	}
	//计算初始总贡献
	sum := 0
	for i := 1; i <= n; i++ {
		if s[i] == '0' {
			continue
		}
		fa := find(i)
		if vis[fa] {
			continue
		}
		vis[fa] = true
		sum += siz[fa] * (siz[fa] - 1) / 2
	}
	ansVal, ansIdx := 0, 0
	for i := 1; i <= n; i++ {
		if s[i] == '1' {
			continue
		}
		tmpSum, nowCnt := sum, 1
		mp := make(map[int]int)
		for _, ne := range grid[i] {
			if s[ne] == '0' {
				continue
			}
			fne := find(ne)
			if _, ok := mp[fne]; ok {
				continue
			}
			mp[fne] = 1
			tmpSum -= siz[fne] * (siz[fne] - 1) / 2 //减去原先联通块的贡献
			nowCnt += siz[fne]
		}
		tmpSum = tmpSum + nowCnt*(nowCnt-1)/2 //加上新联通块数量
		if ansVal < tmpSum {
			ansVal = tmpSum
			ansIdx = i
		}
	}
	fmt.Printf("%d %d",  ansIdx,ansVal)
}