Loner John 的博客
0%

csuoj-算法-Battle_Over_Cities

发表于 更新于 分类于 Valine：

题目

解题思路

题目的意思可以理解为：求去掉关键城市后连通图的数量。
想到的做法有两种。

  • 通过DFS计算数量
  • 用并查集计算数量

Java解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
法一：DFS
	import java.util.Scanner;
	
	public class Main {
	    int N,M,K;
	    boolean []black;
	    boolean [][]edge;
	    int []kCity,ansK;
	    Main(){
	        Scanner scanner = new Scanner(System.in);
	        N=scanner.nextInt();
	        M= scanner.nextInt();
	        K=scanner.nextInt();
	        black=new boolean[N+1];
	        edge =new boolean[N+1][N+1];
	        kCity=new int[K];
	        ansK=new int[N+1];
	        for (int i = 0; i < M; i++) {
	            int h=scanner.nextInt(),l= scanner.nextInt();
	            edge[h][l]=true;
	            edge[l][h]=true;
	        }//初始化
	        for (int i = 0; i < K; i++) {
	            kCity[i]=scanner.nextInt();
	        }//初始化
	        for (int i = 1; i < ansK.length; i++) {
	            ansK[i]=-1;
	        }//初始化
	    }
	    public void ex(){
	        for (int i = 0; i < K; i++) {
	            if (ansK[kCity[i]]!=-1)continue;
	            int ans=0;
	            for (int i1 = 1; i1 < black.length; i1++) {
	                black[i1]=false;
	            }
	            black[kCity[i]]=true;//将关键点（城市）标记为遍历过的点
	            for (int j = 1; j < N+1; j++) {
	                if(black[j]==false){
	                    dfs(j);
	                    ans++;
	                }
	            }
	            ansK[kCity[i]]=ans;
	        }
	    }
	    public void dfs(int j){
	        black[j]=true;
	        for (int i = 1; i < N+1; i++) {
	            if(edge[i][j]&&!black[i]){
	                dfs(i);
	            }
	        }
	    }
	    public static void main(String[] args) {
	        Main main = new Main();
	        main.ex();
	        for (int i : main.kCity) {
	            System.out.println(main.ansK[i]-1);
	        }
	    }
	}
1
2
法二：并查集
	哎呀，好懒，下次再写。