802. 找到最终的安全状态

有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。

如果一个节点没有连出的有向边，则它是 终端节点 。如果没有出边，则节点为终端节点。如果从该节点开始的所有可能路径都通向 终端节点 ，则该节点为 安全节点 。

返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。

示例 1：

Illustration of graph

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
节点 5 和节点 6 是终端节点，因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。

示例 2：

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
解释:
只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。

非安全节点一定是可以形成环的，根据这个原理，我们就可以得到最终的解题思路，判断一个节点是否会形成环：
解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
  
 int dfs(int *r,int** graph, int graphSize, int* graphColSize,int now_po,int *l){

   if(r[now_po]==1||r[now_po]==2){
       return 2;
   }
    if(l[now_po]==1){
        return -1;
    }
     if(r[now_po]==-1){
        return -1;
    }
    l[now_po]=1;
     
    int i=0;
     for( i=0;i<graphColSize[now_po];i++){
        
      
         if(graph[now_po][i]==now_po){
            l[now_po]=0;
             return -1;
         }

         if(r[graph[now_po][i]]==2||r[graph[now_po][i]]==1){
             continue;
         }
         else{
            
             
             if(dfs(r,graph,graphSize,graphColSize,graph[now_po][i],l)==2){
                 continue;
             }
             else{
                 break;
             }
         }
     }
     l[now_po]=0;
  
     if(i==graphColSize[now_po]){
          r[now_po]=2;
         return 2;
     }
     else{
         r[now_po]=-1;
         return -1;
     }

 }

int* eventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize){
    int *r=(int *)malloc(sizeof(int)*graphSize);
     int *l=(int *)malloc(sizeof(int)*graphSize);

    for(int i=0;i<graphSize;i++){

        if(graphColSize[i]==0){
            r[i]=1;
        }
        else{
             r[i]=0;
        }
        l[i]=0;
    }
 
     
    for(int i=0;i<graphSize;i++){
      
       
        if(r[i]==0){
          
          int p= dfs(r,graph,graphSize,graphColSize,i,l);
        }
      
      
    }
    int size=0;
   for(int i=0;i<graphSize;i++){
       if(r[i]==2||r[i]==1){
           size++;

       }
   }
   int *re=(int *)malloc(sizeof(int )*size);
   size=0;
   for(int i=0;i<graphSize;i++){
       if(r[i]==2||r[i]==1){
          re[size++]=i;

       }
   }
   *returnSize=size;
   return re;





}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102