图-找环-在线编程-K6K4.com

给定一个有向带权图A，找出图中的环，返回构成环的所有顶点，并按顶点从小到大排序。
约定：
（1）使用邻接矩阵表示图
（2）若两个顶点i,j相连则A[i][j]=1,否则A[i][j]=0
（3）顶点编号从0开始
（4）图是有向的，需要考虑方向性
（5）图中最多存在一个环

例如：
（1）
矩阵A的邻接矩阵表示为：
0,1,0
0,0,1
1,0,0

图中的环为：0,1,2
（2）
矩阵A的邻接矩阵表示为：
0,1,0
0,0,0
1,1,0

图中不存在环（方向问题）：返回-1

输入、输出描述

输入：

A：有向图的邻接矩阵表示，若两个顶点i,j相连，则A[i][j]=1 否则A[i][j]=0
n：顶点的个数，顶点编号为：0，1，2...n-1

输出：

若存在环，则返回构成环的所有顶点，并按顶点从小到大排序。
若不存在环，则返回一个长度为1的数组，且元素值为-1

Example

输入：

A：
0,1,0
0,0,1
1,0,0
n：3

输出：

0,1,2

修改

基本思路：如果一个顶点p在图中的环上，则必然存在一条以p为起点同时又以p为终点的的轨迹如下：

p->a1->a2->a3->...->ak->p，用DFS递归遍历p点的各个后驱节点，只要判断这条轨迹的最后一个节点是否为p即可，为p则包含环，不为p则不存在环。

代码：

import java.util.*;

public class Main {
  private boolean[] marked;//用来标记节点是否已经被访问
  private int[] edgeTo;//记录当前节点之前路径上的所有节点
  private boolean[] onStack;
  private Stack<Integer> cycle;//记录环上的所有节点，没有环时为空
  
  public int[] solution(int[][] A,int n) {
    cycle = null;
    int[] cyclePointSort = new int[]{-1};
    marked = new boolean[n];
    onStack = new boolean[n];
    edgeTo = new int[n];
    for (int v = 0; v < n; v++)
      if (!marked[v] && cycle == null)
        dfs(A, n, v);
    if (cycle != null) {
      cycle.pop();//起点和终点是同一个点，将终点出栈
      int cycleSize = cycle.size();
      cyclePointSort = new int[cycleSize];
      int i = 0;
      for (int point : cycle)
        cyclePointSort[i++] = point;
      
      Arrays.sort(cyclePointSort);
    }
    return cyclePointSort;
  }
  
  private void dfs(int[][] A, int n, int v) {
    onStack[v] = true;
    marked[v] = true;
    for (int i = 0; i < n; i++) {
      if (A[v][i] == 1) {
        if (cycle != null)
          return;
        else if (!marked[i]) {
          edgeTo[i] = v;
          dfs(A, n, i);
        }
        else if (onStack[i]) {
          cycle = new Stack<Integer>();
          for (int x = v; x != i; x = edgeTo[x]) {
            cycle.push(x);
          }
          cycle.push(i);
          cycle.push(v);
          assert check();
        } 
      }
    }
    onStack[v] = false;
  }
  
  public boolean hasCycle() {
    return cycle != null;
  }
  
  public Iterable<Integer> cycle() {
    return cycle;
  }
  
  private boolean check() {
    if (hasCycle()) {
      int first = -1, last = -1;
      for (int v : cycle()) {
        if (first == -1)
          first = v;
        last = v;
      }
      if (first != last) {
        return false;
      }
    }
    return true;
  }
  
}