CCF-CSP 201709-4通信网络
问题描述
某国的军队由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。
解题思路：
用一个isconnect二维数组来存储两边是否能够相互到达，能为1，不能为0，然后用dfs遍历所有的点，
首先声明，dfs一定会便利所有的和它互通的点的 是吧！<*-*>
代码如下：
import java.util.Scanner;
public class communication1 {
static int isconnect[][] = new int [1001][1001];
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int result=0;
int n = sc.nextInt();
int m = sc.nextInt();
int a[][] = new int[m][2];
for(int i= 0 ; i < m ; i++){
a[i][0]=sc.nextInt();
a[i][1]=sc.nextInt();
}
for(int v = 1 ;v<=n ; v++){
int book[] = new int [n+1];
dfs(v,a,n,v,book,m);
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
if(isconnect[i][j]==0)
break;
if(j==n) //在矩阵中找到与其他所有点都相连的点
result++;
}
}
System.out.println(result);
}
private static void dfs(int v, int[][] a, int n, int cur, int book[],int m) {
// TODO Auto-generated method stub
isconnect[v][cur]=isconnect[cur][v]=1;
for(int j = 0; j<m ; j++){
if(a[j][0]==cur&&book[a[j][1]]==0){
book[cur]=1; //标记
cur=a[j][1]; //点的移动
isconnect[v][cur]=isconnect[cur][v]=1;
dfs(v,a,n,cur,book,m); //这里可以取消标记也可以不取消标记的
cur=a[j][0]; //回到上一次的出发点
}
}
}
}
但是很遗憾，这样做复杂度太高了，只能拿到60分
解法二：
解题思路：运用邻接表的思想，不了解的可以先了解一下邻接表的基本概念<*-*>,邻接表对于稀疏图还是有优势的，然后同样用dfs遍历。
代码如下：
import java.util.Scanner;
import java.util.ArrayList;
public class communication{
static int [][]isconnect = new int[1024][1024];
@SuppressWarnings(“rawtypes”)
static ArrayList[]arraylist= new ArrayList[1024];
@SuppressWarnings(“unchecked”)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int result=0;
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 1; i<=n ;i++ ){
arraylist[i]=new ArrayList<Integer>();
}
for(int i=0; i<m ; i++){
int s,e;
s=sc.nextInt();
e=sc.nextInt();
arraylist[s].add(e); //该图为有向图，数组下标为起始点，对应集合中的元素为和它相连的终点
}
for(int i = 1;i<=n;i++){ //对每个点作为出发点进行遍历
int[] book = new int [n+1];
dfs(book,i,i,i);
}
for(int i = 1; i<=n ; i++){
int j ;
for(j = 1;j<=n;j++){
if(isconnect[i][j]==0){
break;
}
if(j==n){
result++;
}
}
}
System.out.println(result);
}
public static void dfs(int book[],int cur,int v,int mid){
book[cur]=1;
isconnect[v][cur]=isconnect[cur][v]=1;
for(int i = 0 ; i<arraylist[cur].size() ; i++){
if(book[Integer.parseInt(String.valueOf(arraylist[cur].get(i)))]==0){
mid = cur;
cur=Integer.parseInt(String.valueOf(arraylist[cur].get(i)));
dfs(book,cur,v,mid); //这里没必要要取消标记，因为我们是要
cur=mid;
}
}
}
}
这样就降低了算法复杂度，就拿到100分啦！<*-*>