博弈论(sg函数)

帅哥函数的板子题，求sg函数这边用了拓扑排序和二进制集合运算（个人认为比dfs好写一点，而且不会爆栈）

sg函数单子必胜条件： sg[node] != 0

sg函数多子必胜条件： 0^ sg[node1] ^ sg[node2] ^ … sg[noden] != 0

python版本 （利用拓扑排序）

推销一下下面的个人发明建边函数def Lin(a,b)（我称之为琦氏建边法），速度虽然比纯append来的慢，但是可以稳定的去重边和取最优重边，给用python写图论的兄弟们安利一下=_+

# 多人sg函数
def Lin(a,b):
    if a not in link.keys():
        link[a] = {b}
        ind[b] += 1
    else:
        if b not in link[a]:
            ind[b] += 1
            link[a].add(b)

def topSort():
    queue = []
    for i in range(1,n+1):
        if ind[i] == 0:
            queue.append(i)
    while queue:
        curNode = queue.pop(0)

        if curNode not in link.keys():
            continue
        for node in link[curNode]:
            ind[node] -= 1
            sto[node] |= 1 << sg[curNode]
            if ind[node] == 0:
                sg[node] = 0
                while sto[node] & 1:
                    sg[node] += 1
                    sto[node] >>= 1
                queue.append(node)

n,m,k = map(int,input().split())
link = {}
ind = [0]*(n + 1)
for i in range(m):
    a,b = map(int,input().split())
    Lin(b,a)

startNodes = [int(i) for i in input().split()]

sg = [0]*(n + 1)
sto = [0]*(n + 1)
topSort()

res = 0
for i in range(k):
    res ^= sg[startNodes[i]]

if res:
    print('win')
else:
    print('lose')