Submission #4071119

---

Source Code Expand

N,C,E = map(int, input().split())
girls = map(int, input().split())
e = []
for _ in range(E):
    a,b = map(int, input().split())
    e.append((a,b))

visit = [False]*N
def dfs(i:int):
    global visit,e
    if visit[i]: return
    else: visit[i] = True
    # print(i)
    nex = []
    for ej in e:
        if ej[0]==i:   nex.append(ej[1])
        elif ej[1]==i: nex.append(ej[0])
    for nexi in nex:
        dfs(nexi)

        
ans  = 1e9
for comb in range(1<<E):
    cnt = 0
    cur_e = []
    visit = [False]*N
    for j in range(E):
        if (comb>>j)&1==1: cur_e.append(e[j])
        else:  cnt += 1
    # print(cur_e)

    dfs(0)
    cnt = 0
    for gi in girls:
        if not visit[gi]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Submission Info

Judge Result