java - 如何在有向图中找到凹坑？

问题：我们有一个有向图，如何在一个图上找到一个孔（坑）（n）时间复杂度。
图上的凹坑：如果一个顶点的n-1度表示（输入），0度表示（输出），我们就有一个图上的凹坑。

最佳答案

我认为你根本不需要搜索图表。
您只需计算每个节点的独立度和超出度您只需查找节点的节点索引为（n-1）且outdegree为“0”。
考虑到你知道有多少边。

int outdegree[n]={0}; // Storing outdegree of each node
int indegree[n]={0}; /// Storing indegree of each node


 while(m--)  // m is number of edges
 {
    scanf("%d %d",&a,&b);  // this means there is an edge from 'a' to 'b'. a-->b
    outdegree[a]++;
    indegree[b]++;
 }
 int sink;
 for(i=1;i<=n;i++)
 {
    if((outdegree[i]==0 )&& (indegree[i]==(n-1)))
        sink=i;
 }
 cout<<"Sink/Pit is: "<<sink<<endl;