提出 #37357012

---

ソースコード 拡げる

from collections import defaultdict
from copy import deepcopy
class DSU():
    def __init__(self):
        self.dsu = defaultdict(lambda: -1)
    
    def leader(self, i):
        if self.dsu[i] < 0: return i
        self.dsu[i] = self.leader(self.dsu[i])
        return self.dsu[i]

    def merge(self, i, j):
        '''サイズの大きい方(x)に小さい方(y)をマージ'''
        if i == j: return
        x = self.leader(i)
        y = self.leader(j)
        if x == y: return

        if self.dsu[x] > self.dsu[y]: x, y = y, x

        self.dsu[x] += self.dsu[y]
        self.dsu[y] = x
    
    def members(self, i):
        l = self.leader(i)
        return [k for k, v in self.dsu.items() if self.leader(k) == l]

    
def D(N, M, uv):
    dsu = DSU()
    g = DSU()
    edge = defaultdict(list)
    for u, v in uv:
        dsu.merge(u, N + v)
        dsu.merge(N + u, v)
        g.merge(u, v)
        edge[u].append(v)
        edge[v].append(u)
    
    leaders = dict()
    for i in range(1, N + 1):
        l = g.leader(i)
        if l in leaders: continue
        
        for n in g.members(l):
            if dsu.leader(n) == dsu.leader(n + N):
                leaders[l] = False
                break
        else:
            leaders[l] = True
        
    ans = 0
    for i in range(1, N + 1):
        e = edge[i]
        for j in range(i + 1, N + 1):
            if j in e: continue
            
            li = g.leader(i)
            lj = g.leader(j)
            
            if li != lj:
                if leaders[li] and leaders[lj]:
                    ans += 1
                    continue
                else:
                    continue
            
            if not leaders[li]:
                continue
            
            target = deepcopy(dsu)
            target.merge(i, N + j)
            target.merge(N + i, j)
            for k in [i, j]:
                if target.leader(k) == target.leader(k + N): break
            else:
                ans += 1
    
    return ans

N, M = map(int, input().split())
uv = list(list(map(int, input().split())) for _ in range(M))
print(D(N, M, uv))

提出情報

ジャッジ結果