题解 | #All-Star Game#

很多大佬都写过这题的题解 我就提供一下python AC的方式吧 离散化过程有两种写法，一种是比较标准的去重、排序加二分，另一种就是比较懒直接用字典存图和用字典vis。

一开始建图对每个连通块的遍历想的是dfs，简单嘛，但爆栈了，加栈后超时，段错误..... 所以改成了bfs， emmm用了queue库的Queue当队列超时，后来想了想这个支持多线程 肯定慢啊QAQ。得改成collections库的deque当队列使用 AC 了。 下面分别给出pypy3离散化 和 字典的代码吧

贴出两种的用时：

离散化的AC代码

import sys
from collections import deque

def bfs(r):
    global cnt1,cnt2
    q = deque()
    q.append(r)
    while q:
        x = q.popleft()
        if vis[x]: continue
        vis[x] = True
        cnt1 += 1
        for y in g[x]:
            cnt2 += 1
            q.append(y)
        
def find(x):
    l,r = 0, len(alls)
    while l < r:
        mid = (l+r)//2
        if alls[mid] >= x: r = mid
        else: l = mid + 1
    return r

t = int(sys.stdin.readline())
case = 0
while t > 0:
    t -= 1
    case += 1
    n = int(sys.stdin.readline())
    alls,ls = [],[]
    ans = 0
    for _ in range(n):
        a,b = map(int, sys. stdin.readline().split())
        ls.append((a,b))
        alls.append(a)
        alls.append(b)
    alls = sorted(set(alls))
    g = {i: [] for i in range(len(alls)+1)}
    for i in range(len(ls)):
        a,b = ls[i]
        a,b = find(a),find(b)
        g[a].append(b)
        g[b].append(a)
    vis = [False]*(len(alls)+1)
    for i in range(len(alls)):
        cnt1,cnt2 = 0,0
        if not vis[i]:
            bfs(i)
            ans += min(cnt1,cnt2//2)
    print(f'Case #{case}: {ans}')

用字典的AC代码

import sys
from collections import deque

def bfs(r):
    global cnt1,cnt2
    q = deque()
    q.append(r)
    while q:
        x = q.popleft()
        if x in vis: continue
        vis.add(x)
        cnt1 += 1
        for y in g[x]:
            cnt2 += 1
            q.append(y)


t = int(sys.stdin.readline())
case = 0
while t > 0:
    t -= 1
    case += 1
    n = int(sys.stdin.readline())
    g, ans = {}, 0
    for i in range(n):
        x,y = map(int, sys.stdin.readline().split())
        if x in g: g[x].append(y)
        else: g[x] = [y]
        if y in g: g[y].append(x)
        else: g[y] = [x]
    vis = set()
    for i in g:
        cnt1,cnt2 = 0,0
        if i not in vis:
            bfs(i)
            ans += min(cnt1,cnt2//2)
    print(f'Case #{case}: {ans}')