图找环，递归、拓扑排序

题目： 找到最终的安全状态

递归法

bool isSafe(int** graph, int graphSize, int* graphColSize, int index, int *color);

int* eventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize){

    //务必要初始化
    int *color = (int *)malloc(sizeof(int)*graphSize);
    memset(color, 0, sizeof(color));//初始化为0

    *returnSize = 0;
    int *res = (int *)malloc(sizeof(int)*graphSize);
    for(int i=0; i<graphSize; i++) {
        if (isSafe(graph, graphSize, graphColSize, i, color)) {
            res[(*returnSize)++] = i;
        }
    }
    
    return res;
}

bool isSafe(int** graph, int graphSize, int* graphColSize, int index, int *color)
{
    if (color[index] == 1) {
        return false;
    } else if(color[index] == 2) {
        return true;
    }

    color[index] = 1;//设定为已存在
    for(int i=0; i<graphColSize[index]; i++) {
        if (!isSafe(graph, graphSize, graphColSize, graph[index][i], color)) {
            return false;
        }
    }
    color[index] = 2;  //标记为安全
    return true;
}

拓扑排序法

bool isSafe(int ** graph, int graphSize, int * graphColSize, int index);

int* eventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize){

   *returnSize = 0;
   int *res = (int *)malloc(sizeof(int)*graphSize);
   for(int i=0; i<graphSize; i++) {
       //逐个去判断当前点 相关的图是否存在环，会比较慢，数据量大会超时
       if (isSafe(graph, graphSize, graphColSize, i)) {
           res[(*returnSize)++] = i;
       }
   }
   
   return res;
}

bool isSafe(int ** graph, int graphSize, int * graphColSize, int index)
{
   //计算所有点的入度
   int V[graphSize],exists[graphSize];
   for(int i=0; i<graphSize; i++) {
       V[i] = -1;          //默认标记为-1，可能部分点没参与图
   }
   memset(exists, 0, sizeof(exists));  //标记是否已访问过

   //模拟一个栈 用于计算所有有关联点的入度
   int stack[graphSize*2];
   int top = -1;
   V[index] = 0;
   for(int i=0; i<graphColSize[index]; i++) {
       stack[++top] = graph[index][i];
       if (V[graph[index][i]] == -1) {
           V[graph[index][i]] = 1;
       } else {
           V[graph[index][i]]++;
       }
   }
   exists[index] = 1;
   while(top >= 0) {
       int cur = stack[top--];
       if (exists[cur] == 0) {
           for(int i=0; i<graphColSize[cur]; i++) {
               stack[++top] = graph[cur][i];
               if (V[graph[cur][i]] == -1) {
                   V[graph[cur][i]] = 1;
               } else {
                   V[graph[cur][i]]++;
               }
           }
           exists[cur] = 1;
       }
   }
   // printf("index:%d\n", index);
   // for(int i=0; i<graphSize; i++) {
   //     printf("%d ", V[i]);
   // }
   // printf("\n");

   while(true) {
       //任意找一个入度为0的 并删掉，如果找不到 判断是否有入度大于0的点存在
       bool isExistZero = false;
       for(int i=0; i<graphSize; i++) {
           if (V[i] == 0) {
               //存在入度为0的，删掉点，并扣掉入度
               isExistZero = true;
               V[i] = -1;
               for(int j=0; j<graphColSize[i]; j++) {
                   V[graph[i][j]]--;
               }
               i = graphSize;
           }
       }
       if (!isExistZero) {
           //不存在 检测是否还有入度大于0的点，如果有，表示有环，不安全
           for(int i=0; i<graphSize; i++) {
               if (V[i] > 0) {
                   return false;
               }
           }
           return true;
       }
   }
   return true;
}

拓扑排序 逆向法

解法：从题目可知，1：如果一个点，没有出度，即为安全的点；2：如果一个点，所有出度指向的都是安全的点，那么这个点也是安全的点。
将原有图逆序，然后做拓扑排序，不能参与排序的点，即为不安全的点

int* eventualSafeNodes(int** graph, int graphSize, int* graphColSize, int* returnSize){

    *returnSize = 0;
    int *res = (int *)malloc(sizeof(int)*graphSize);
    
    //逆转方向 进行拓扑排序，剩余的就是不安全的点
    //逆转方向后，统计各点的入度
    int arr[graphSize];
    memset(arr, 0, sizeof(arr));
    //逆向图 方便后续处理
    int G[graphSize][100];//默认最大100 如果是graphSize*graphSize 会导致空间占用过大
    int size[graphSize];
    memset(G, 0, sizeof(G));
    memset(size, 0, sizeof(size));

    for(int i=0; i<graphSize; i++) {
        //计算 逆向后的入度
        arr[i] += graphColSize[i];
        //生成逆向后的图信息
        for(int j=0; j<graphColSize[i]; j++) {
            int key = graph[i][j];
            G[key][size[key]++] = i;
        }
    }
    bool isExistZero = true;
    while(isExistZero) {
        isExistZero = false;
        //取出一个入度为0的 删除 并将关联的入度减1
        for(int i=0; i<graphSize; i++) {
            if(arr[i] == 0) {
                isExistZero = true;
                //标记删除
                arr[i] = -1;
                //将逆向指向的相关点 减1
                for(int j=0; j<size[i]; j++) {
                    int key = G[i][j];
                    arr[key]--;
                }
            }
        }
    }
    //输出入度标记为-1的 即为安全的
    for(int i=0; i<graphSize; i++) {
        if (arr[i] == -1) {
            res[(*returnSize)++] = i;
        }
    }
    return res;
}