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

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

提取码: 5ti7

假设邻接矩阵为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

#include <stdio.h>
#include <string.h>
#define MAX 100 //顶点的最大个数
 
 
int Edge[MAX][MAX];//邻接矩阵
 
int main()
{
    
    int i,j;//循环变量
    int n,m;//顶点个数，边数
    int u,v;//边的起点和终点
    int od,id;//顶点的出度和入度
    int mark = 0; //若有这样的点，则置1
    printf("请输入顶点个数和边数\n");
    scanf("%d %d",&n,&m);//读入顶点个数n和边数m
    
    if(n == 0 && m == 0)
    {
        return 0;
    }
    memset(Edge,0,sizeof(Edge));
    for(i = 1; i <= m; i++)
    {
        printf("请输入边的起点和终点\n");
        scanf("%d %d",&u,&v);//读入边的起点和终点
        Edge[u - 1] [v - 1] = 1;//构造邻接矩阵
        
    }
    
    for(i = 0; i < n; i++)
    {
        od = 0;//求各顶点的出度
        id = 0;//求各顶点的入度
        for(j = 0; j < n; j++)
        {
            od += Edge[i][j];
            id += Edge[j][i];
        }
        if(id == n-1 && od == 0) 
     	{
		    mark = 1;
		    break; 
	    } 
    }
    
    if(mark)
    {
		printf("存在这样一个v\n");
	}
	else
	{
		printf("不存在这样一个v\n");
	}
	
    return 0;
}

没有想到可以O(n)就能处理这道问题的办法。不愧是三十分的大题啊。