本文共 2367 字，大约阅读时间需要 7 分钟。

DFS（AC）

import java.util.ArrayList;import java.util.Scanner;public class Main {	static ArrayList
   
     []adj;	static int n, m;	static int tol;	static boolean []vis;	static boolean [][]isLinked;	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		n = in.nextInt(); 		m = in.nextInt(); 		adj = new ArrayList[n+1]; 		vis = new boolean[n+1]; 		isLinked = new boolean[n+1][n+1]; 		for(int i = 1; i <= n; i++ ) { 			adj[i] = new ArrayList<>(); 		} 		tol = 0; 		for(int i = 1; i <= m; i++ ) { 			int a = in.nextInt(); 			int b = in.nextInt(); 			adj[a].add(b); 		} 		for(int i = 1; i <= n; ++i) { 			for(int j = 1; j <= n; ++j)//搜索每个点之前 要把vis置false 				vis[j] = false; 			dfs(i, i); 		} 		int i, j; 		for(i = 1; i <= n; ++i) { 			for(j = 1; j <= n; ++j) { 				if(!isLinked[i][j])//不满足条件 直接退出 					break; 			} 			if(j == n+1) 				tol++; 		} 		System.out.println(tol); 			}	public static void dfs(int v,int cur) {//核心		vis[v] = true;		isLinked[v][cur] = isLinked[cur][v] = true; //从cur开始搜的每个点 都是与其相连接的 可以通信				for(int w:adj[v]) {//搜索 v的每个临接点			if(!vis[w]) {				dfs(w,cur);//注意 这里 cur实际上 只是 用于 记录搜索路径上的点 与最初的cur可以通信			}		}			}}
   

另外 之前用的另一种思路 一直没有AC  先放上 有时间再找找原因

想着是从图的正向 和反向分别DFS 然后 如果 所有的 点 都被访问 说明 该点 可以与所有点通信

但是 不能AC  还没发现问题在哪。。。

package CSP2017_9;import java.util.ArrayList;import java.util.Scanner;public class Main {	static ArrayList
   
     []adj;	static ArrayList
    
      []list;	static int n, m;	static int tol;	static boolean []vis;	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		n = in.nextInt(); 		m = in.nextInt(); 		adj = new ArrayList[n+1]; 		list = new ArrayList[n+1]; 		vis = new boolean[n+1]; 		for(int i = 1; i <= n; i++ ) { 			list[i] = new ArrayList<>(); 		} 		for(int i = 1; i <= n; i++ ) { 			adj[i] = new ArrayList<>(); 		} 		tol = 0; 		for(int i = 1; i <= m; i++ ) { 			int a = in.nextInt(); 			int b = in.nextInt(); 			adj[a].add(b); 			list[b].add(a); 		} 		 		for(int i = 1; i <= n; i++ ) { 			int cnt = 0; 			dfs(i,adj); 			dfs(i,list); 			for(int j = 1; j <= n; j++ ) { 				if(vis[j]) 					cnt++; 				vis[j] = false; 			} 			if(cnt == n) { 				tol++; 				//System.out.println("point:" + i); 			} 		} 		 		System.out.println(tol); 			}	public static void dfs(int cur, ArrayList
     
       []adj) {		vis[cur] = true;		for(int w : adj[cur]) {			if(!vis[w]) {				dfs(w,adj);			}		}	}}
     
    
   

转载地址：http://elimi.baihongyu.com/