小猿的依赖循环

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            // 构建邻接矩阵
            int n = Integer.parseInt(br.readLine());
            int[][] graph = new int[n][n];
            for(int i = 0; i < n; i++){
                String[] row = br.readLine().split(" ");
                for(int j = 0; j < row.length; j++)
                    graph[i][j] = Integer.parseInt(row[j]);
            }
            // 判断是否是有向无环图
            System.out.println(isDag(graph)? 1: 0);
        }
    }
    
    public static boolean isDag(int[][] graph) {
        int nodeNum = graph.length;
        // 记录每个有入度的节点，及其所有的前序节点
        Map<Integer, List<Integer>> inEdge = new HashMap<>(nodeNum);
        // 记录每个节点的出度个数
        int[] outEdgeNum = new int[nodeNum];
        // 初始化数据
        for(int i = 0; i < nodeNum; i++){
            for(int j = 0; j < nodeNum; j++){
                if(graph[i][j] != 0){
                    outEdgeNum[i]++;
                    if(inEdge.get(j) == null){
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        inEdge.put(j, list);
                    }else
                        inEdge.get(j).add(i);
                }
            }
        }
        // 已访问的节点
        Set<Integer> visitedSet = new HashSet<>(nodeNum);
        // 循环遍历所有节点的出度
        while(visitedSet.size() < nodeNum){
            for(int i = 0; i < nodeNum; i++){
                if(outEdgeNum[i] == 0 && !visitedSet.contains(i)){
                    visitedSet.add(i);
                    for(int temp = 0; inEdge.get(i) != null && temp < inEdge.get(i).size(); temp++)
                        outEdgeNum[inEdge.get(i).get(temp)]--;
                    break;
                }
                // 节点遍历一遍后，判断是否访问了过所有节点
                if((i == nodeNum - 1) && visitedSet.size() != nodeNum)
                    return true;
            }
        }
        return false;
    }
}

T = int(input())
from collections import deque
def help(arr):
    N = len(arr)
    adj = [[] for _ in range(N)]
    degree = [0] * N
    for i in range(N):
        for j in range(N):
            if arr[i][j]:
                degree[i] += 1
                adj[j].append(i)
    queue = deque()
    for i in range(N):
        if not degree[i]:
            queue.append(i)
    while queue:
        node = queue.popleft()
        for x in adj[node]:
            degree[x] -= 1
            if degree[x] == 0:
                queue.append(x)
    if sum(degree) == 0:
        return 1
    else:
        return 0
for _ in range(T):
    N = int(input())
    arr = []
    for i in range(N):
        arr.append(list(map(int, input().split())))
        print(help(arr))

def dfs(arr, visit, idx, ht):
    if sum(arr[idx]) == 0:
        return False 
    #print(ht)
    ht[idx] = 1
    for i in range(len(arr[idx])):
        if arr[idx][i] == 1:
            if ht[i] == 1: #already visit => loop 
                return True 
            else:
                ht[i] = 1 
                visit[i] = 1 
                if dfs(arr, visit, i, ht):
                    return True 
                ht[i] = 0 
    ht[idx] = 0
    return False 

T = input() 
while T > 0:
    N = input()
    arr = []
    while N > 0:
        arr.append(map(int, raw_input().strip().split(' ')))
        N -= 1 
    visit = [0] * len(arr) 
    ht = [0] * len(arr) 
    flag = 0
    for i in range(len(arr)):
        if visit[i] == 0:
            if dfs(arr, visit, i, ht):
                print(1)
                flag = 1
                break 
    if flag == 0:
        print(0)
    T-= 1

    

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool dfs( vector<vector<int>>& sour, vector<int>& isOk, int n, int i )
{
    isOk[i] = 1;
    for ( int j = 0; j < n; ++j )
    {
        if ( sour[i][j] == 1 )
        {
            if ( isOk[j] == 1 || !dfs(sour,isOk,n,j) )
                return false;
        }
    }
    isOk[i] = 2;
    return true;
}
int main()
{
    int times;
    cin >> times;
    for ( int i = 0; i < times; ++i )
    {
        int size;
        cin >> size;
        vector<vector<int>> sour(size,vector<int>(size));
        vector<int> isOk(size,0);
        for ( int j = 0; j < size; ++j )
        {
            for ( int k = 0; k < size; ++k )
            {
                cin >> sour[j][k];
            }
        }
        bool isGood = true;
        for ( int i = 0; i < size; ++i )
        {
            if ( isOk[i] != 2 && !dfs(sour,isOk,size,i) )
            {
                isGood = false;
                break;
            }
        }
        if (isGood)
        {
            cout << 0;
        }
        else
        {
            cout << 1;
        }
        if ( i != times - 1 )
            cout << endl;
    }
    return 0;
}