Atcoder ABC231 振り返り

　バーチャルで参加しました(221位)．Union Findはいつかちゃんと実装しないとなと思っていたので今回これを使う問題が出てきて良かったです．

A - Water Pressure【AC】

　言われたことをそのまま実装するだけです．

D = int(input())
print(D/100)

B - Election【AC】

　辞書を使って投票人数をカウントします．keyが存在しないときsetdefaultを使うと簡単にkeyをvalueを設定できます．

S = int(input())
dic = {}

for _ in range(S):
    name = input()
    dic.setdefault(name, 0)
    dic[name] += 1

v = 0
for key, values in dic.items():
    if values > v:
        k = key
        v = values
print(k)

C - Counting 2【AC】

　二分探索を使います．二分探索はソートされた数列に対して，新しい数をソートを乱さないように挿入するには何番目に挿入すればいいかを計算量log nで求めてくれます．

import bisect
N, Q = map(int, input().split())
A = sorted([int(i) for i in input().split()])

for _ in range(Q):
    x = int(input())
    print(N-bisect.bisect_left(A, x))

D - Neighbors【AC】

　人がどう繋がっていたら直線じゃなくなるかを考えます．一つ目のパターンはとある人1人に対して3人以上繋がっていた場合です．
これは隣接リストを使って要素が3つ以上あったら検出できます．
　二つ目のパターンは複数人でループしていた場合です．

これは隣接リストを見るだけでは検出できません．今回はUnion Findを使います．
　Union Findでは，あるノードとあるノードがいくつかのノードを経て繋がっているかどうかを高速で判定してくれます．あるノードとノードを繋げようとしたとき，既にそのノード達が繋がっていたら追加で辺を加えて繋げることになり，そこが閉路になります．これによって閉路を見つけることが出来ます．
　直線でなくなるパターンはこの二つなのでこれを見つけることが出来れば良いです．

N, M = map(int, input().split())
node = [[] for _ in range(N)]
par = [i for i in range(N)]
rank = [0]*(N)
ok = True

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def same(x, y):
    return find(x) == find(y)

for _ in range(M):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    node[a].append(b)
    node[b].append(a)
    if same(a, b):
        ok = False
    else:
        unite(a, b)
    
for i in range(N):
    if len(node[i]) >= 3:
        ok = False
        break
    
print("Yes" if ok else "No")