判断是否成环 JAVA 代码实现

 

import java.util.LinkedList;import java.util.Scanner;public class Hello{	static int[][]mp;	static int[] indegree;	static int N, M;	static LinkedList
     
       list = new LinkedList
      
       ();		public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		N = sc.nextInt();		M = sc.nextInt();		mp = new int[N][N];		indegree = new int[N];		for(int i = 0; i < N; i ++) {			indegree[i] = 0;			for(int j = 0; j < N; j ++) {				mp[i][j] = 0;			}		}				int x, y;		for(int i = 0; i < M; i ++) {			x = sc.nextInt();			y = sc.nextInt();			if(mp[x][y] == 0) {				mp[x][y] = 1;				indegree[y] ++;			}		}				topSort();			}		private static void topSort() {		int cnt = 0;		for(int i = 0; i < N; i ++) {			if(indegree[i] == 0) {				list.addFirst(i);				indegree[i] = -1;			}		}				while(!list.isEmpty()) {			int p = list.removeFirst();			System.out.print(p + " ");			cnt ++;			for(int j = 0; j < N; j ++) {				if(mp[p][j] == 1) {					mp[p][j] = 0;					indegree[j] --;					if(indegree[j] == 0) {						list.addFirst(j);						indegree[j] = -1;					}				}			}		}				System.out.println();		if(cnt < N) System.out.println("Cycleeeeee!");		else System.out.println("Nooooooooo!");			}	}
      
     

 

　　但是上述是建立邻接矩阵的写法 当 N 太大的时候就不是很好了 所以可以用链表来存边和边的关系 会节省内存 所以以下是链表存图并判断拓扑关系

 

import java.util.concurrent.ArrayBlockingQueue;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Hello{		static int N, M;	static int[] v;	static int[] nx;	static int[] h;	static int[] ans;	static int[] in;	static int cnt, sz;	static LinkedList
     
       list = new LinkedList
      
       ();		public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		v = new int[100010];		nx = new int[100010];		h = new int[100010];		in = new int[100010];		N = sc.nextInt();		M = sc.nextInt();				init();				for(int i = 0; i < M; i ++) {			int x, y;			x = sc.nextInt();			y = sc.nextInt();			add(x, y);		}				topSort();			}		public static void init() {		for(int i = 0; i < 100010; i ++) {			h[i] = -1;			in[i] = 0;		}				sz = 0;			}		public static void add(int a, int b) {		v[sz] = b;	    nx[sz] = h[a];	    h[a] = sz;	    in[b] ++;	    sz ++;	}		public static void topSort() {		for(int i = 0; i < N; i ++) {			if(in[i] == 0) list.addFirst(i);		}				while(!list.isEmpty()) {			int tp = list.removeFirst();			System.out.print(tp + " ");			cnt ++;						for(int i = h[tp]; i != -1; i = nx[i]) {				in[v[i]] --;				if(in[v[i]] == 0) list.addFirst(v[i]);			}					}				System.out.println();		if(cnt != N) 			System.out.println("Circleeeeeeeeee");		else System.out.println("Noooooooooo");	}	}