另一个算法题，进链接看文本，不限语言c/c++/python，会的留下代码或者写伪代码分析，请带注释

Question

链接: https://pan.baidu.com/s/1UoBp3_mvMvcbADTh1FQd8A

提取码: 5ti7

Answer 1

假设邻接矩阵为g，g[i][j]表示顶点i到顶点j有一条边，那么我们要找的就是这样一个i：第i行全部为0，且第i列除了g[i][i]之外全部为1。我们随便选一对i和j，如果g[i][j]为1的话，那么可以划掉第i行（也就是排除掉了i），如果g[i][j]为1，那么就可以划掉第j列。只要检查一个格子就可以排除掉一个选项，所以运行时间为O(V)。python代码如下：

from collections import deque
def find(g):
    n = len(g)
    vertices = deque(range(n))
    while len(vertices) > 1:
        i = vertices.popleft()
        j = vertices.popleft()
        if g[i][j] == 0:
            vertices.append(i)
        else:
            vertices.append(j)

    # Now there is only one vertex
    # Check row i and column i
    i = vertices[0]
    for j in range(n):
        if g[i][j] != 0:
            return -1
        if i != j and g[j][i] != 1:
            return -1
    return i
    
g=[[0,1,1,1],
   [1,0,0,1],
   [0,0,0,1],
   [0,0,0,0]]
print(find(g)) # 3