当先锋百科网

首页 1 2 3 4 5 6 7

CSP201709-4通信网络

问题描述

试题编号：201709-4
试题名称：通信网络
时间限制：1.0s
内存限制：256.0MB
问题描述：

问题描述

　　某机构由N个部门组成，为了提高安全性，部门之间建立了M条通路，每条通路只能单向传递信息，即一条从部门a到部门b的通路只能由a向b传递信息。信息可以通过中转的方式进行传递，即如果a能将信息传递到b，b又能将信息传递到c，则a能将信息传递到c。一条信息可能通过多次中转最终到达目的地。
　　由于保密工作做得很好，并不是所有部门之间都互相知道彼此的存在。只有当两个部门之间可以直接或间接传递信息时，他们才彼此知道对方的存在。部门之间不会把自己知道哪些部门告诉其他部门。

　　上图中给了一个4个部门的例子，图中的单向边表示通路。部门1可以将消息发送给所有部门，部门4可以接收所有部门的消息，所以部门1和部门4知道所有其他部门的存在。部门2和部门3之间没有任何方式可以发送消息，所以部门2和部门3互相不知道彼此的存在。
　　现在请问，有多少个部门知道所有N个部门的存在。或者说，有多少个部门所知道的部门数量（包括自己）正好是N。

输入格式

　　输入的第一行包含两个整数N, M，分别表示部门的数量和单向通路的数量。所有部门从1到N标号。
　　接下来M行，每行两个整数a, b，表示部门a到部门b有一条单向通路。

输出格式

　　输出一行，包含一个整数，表示答案。

样例输入

4 4
1 2
1 3
2 4
3 4

样例输出

2

样例说明

　　部门1和部门4知道所有其他部门的存在。

评测用例规模与约定

　　对于30%的评测用例，1 ≤ N ≤ 10，1 ≤ M ≤ 20；
　　对于60%的评测用例，1 ≤ N ≤ 100，1 ≤ M ≤ 1000；
　　对于100%的评测用例，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000。

DFS：

import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int n,m;//顶点数，边数
	static List<Integer>[] g;//有向图的邻接矩阵
	static boolean[] used;//访问标记
	static boolean[][] link;//i可到达j(i能获得j的消息)
	
	static void addE(int from,int to){//添加边
		g[from].add(to);
	}
	
	static void dfs(int v,int w){//如果v能到达w，则v能到达w的所有邻接点
		used[w]=true;
		link[v][w]=link[w][v]=true;//v能获得w的消息，那么同时w也能获得v的消息
		for(int i=0;i<g[w].size();i++)
			if(!used[g[w].get(i)])
				dfs(v,g[w].get(i));
	}
	
	static void init(){
		n=sc.nextInt();
		m=sc.nextInt();
		g=new ArrayList[n];
		used=new boolean[n];
		link=new boolean[n][n];
		for(int i=0;i<n;i++)
			g[i]=new ArrayList<Integer>();
		for(int i=0;i<m;i++)
			addE(sc.nextInt()-1,sc.nextInt()-1);
	}
	
    public static void main(String[] args) {
    	init();
    	for(int i=0;i<g.length;i++){
    		Arrays.fill(used,false);
    		dfs(i,i);
    	}
    	int res=0;
    	for(int i=0;i<n;i++){//行标
    		for(int j=0;j<n;j++){//列标
    			if(!link[i][j])
    				break;
    			if(j==n-1)
    				res++;
    		}
    	}
    	System.out.println(res);
    }
}