小猿在加载一个网页,这个网页共需要N个相关资源,这些资源之间有一些依赖关系。如果这些资源中存在循环依赖,我们认为这个网页不能加载成功,否则可以加载成功。存在循环依赖是指,这些资源中存在资源X,X依赖的资源Y直接或间接依赖于X。
你能帮助小猿判断一下这个网页能否加载成功吗?
第一行输入T(T ≤ 10),表示输入T组数据。每组数据第1行,输入一个数N(1 ≤ N ≤ 500)表示该组case有编号为1~N的N项资源。每组数据第2到 N+1 行,输入一个 N*N 的零一矩阵。矩阵第 i 行第 j 列数字为 a[i][j] 表示编号为 i 的资源是否依赖于编号为 j 的资源,1表示依赖,0表示不依赖。数据保证a[i][i] = 0。
输出包含T行,每行输出对应每组case中是否存在循环依赖。存在输出1,不存在输出0。
2 3 0 1 0 0 0 1 1 0 0 3 0 1 0 0 0 0 0 0 0
1 0
第一组数据:1依赖于2,2依赖于3,3依赖于1,存在循环依赖。第二组数据:只有1依赖于2,不存在循环依赖。
//利用栈实现DFS #include <bits/stdc++.h> using namespace std; enum class State { UNDISCOVERED, DISCOVERED, VISITED, }; int main() { int T;//循环次数 cin >> T; while (T--) { int n;//图顶点数 cin >> n; vector<vector<int>> Group(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> Group[i][j]; } } vector<State> visited(n, State::UNDISCOVERED); bool bigF = false;//退出标志 for (int i = 0; i < n; ++i) { if (bigF) break; if (visited[i] != State::VISITED) {//不存在依赖不需要搜索 stack<int> s; s.push(i); visited[i] = State::DISCOVERED; while (!s.empty()) { auto t = s.top(); int flag = 0; for (int j = 0; j < n; ++j) { if (Group[t][j] == 1 && visited[j] == State::UNDISCOVERED) {//依赖j,并且j没被访问 s.push(j); visited[j] = State::DISCOVERED; flag = 1; break; } else if (Group[t][j] == 1 && visited[j] == State::DISCOVERED) {//依赖j,并且j被访问过了 bigF = true; break; } } if (bigF) break; if (flag == 0) {//不存在依赖,弹出栈顶并将标志置为VISITED auto tempT = s.top(); visited[tempT] = State::VISITED; s.pop(); } } } } if (bigF) cout << 1 << endl; else cout << 0 << endl; } }
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; } }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int T = Integer.parseInt(br.readLine()); for(int t=0; t<T; t++){ int n = Integer.parseInt(br.readLine()); int[][] mat = new int[n][n]; for(int i=0; i<n; i++){ String[] s = br.readLine().split(" "); for(int j=0; j<n; j++){ mat[i][j] = Integer.parseInt(s[j]); } } int res = func(mat, n); bw.write(String.valueOf(res)); bw.newLine(); } br.close(); bw.flush(); } public static int func(int[][] mat, int n){ if(n == 0){ return 0; } int[] output = new int[n]; Queue<Integer> queue = new LinkedList<>(); Set<Integer> set = new HashSet<>(); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(mat[i][j] == 1){ output[i]++; } } if(output[i] == 0){ queue.offer(i); set.add(i); } } while(!queue.isEmpty()){ int cur = queue.poll(); for(int i=0; i<n; i++){ if(mat[i][cur] == 1){ output[i]--; if(output[i] == 0){ queue.offer(i); set.add(i); } } } } return set.size() == n ? 0 : 1; } }
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; }