1013 Battle Over Cities (25 分) java

题意：

图问题，意思是在一个无向图中，以城市为顶点，城市之间有高速公路连接着，战争爆发，如果一个城市被敌人占领了，其他城市之间需要用高速公路运送物资，至少要修几条公路。

解题思路：

城市被占领后，本来连通（不一定）着的城市可能变得不再连通了，转化为求连通子图个数问题，即：这些城市之间形成了多少个连通子图（subConnectBranch：int），要把这些连通子图重新连接起来，至少要修subConnectBranch-1条公路。考虑到可能是个稀疏矩阵，于是采用邻接表建图。遍历领接表，每次遍历之前，重置vist[]数组，先把被占领的城市标记了，在未被占领的城市里，先将其标记，再用dfs遍历，如果dfs已完成，发现for循环里还有未标记的城市，还要再重新dfs一次，那么就说明已经产生了连通子图，于是更新subConnectBranch，使之++，直到所有城市均被标记，最后如果连通子图的值为1，则说明这个图除开被占领的城市后依然是连通的，那就不需要修了。个人觉得用bfs也可以达到同样的效果。但是不能ac，最后一个测试点始终超时，但思路感觉是没问题的，以后再用C/C++改写一下代码。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
 public static void main(String[]args) throws IOException {
  
  BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
  String init[] = rd.readLine().split(" ");
  int n = Integer.parseInt(init[0]);
  int m = Integer.parseInt(init[1]);
  int k = Integer.parseInt(init[2]);
  City[] arr = new City[n+1];
  for(int i=1; i<arr.length; i++) {
   arr[i] = new City(i);
  }
  
  for(int i=0; i<m; i++) {
   String str[] = rd.readLine().split(" ");
   int x = Integer.parseInt(str[0]);
   int y = Integer.parseInt(str[1]);
   City p = arr[x];
   while(p.next != null) p = p.next;
   p.next = new City(y);
   City q = arr[y];
   while(q.next != null) q = q.next;
   q.next = new City(x);
  }
  
//  for(int i=1; i<n+1; i++) {
//   City p = arr[i];
//   System.out.print("city " + p.id + ": ");
//   while(p.next!=null) {
//    p = p.next;
//    System.out.print(p.id+" ");
//   }
//   System.out.println();
//  }
  String connect[] = rd.readLine().split(" ");
  for(int j=0; j<k; j++) {
   boolean visit[] = new boolean[n+1];
   int ocp = Integer.parseInt(connect[j]);
   visit[ocp] = true;
   int subConnectBranch = 0;
   for(int i=1; i<n+1; i++) {
    if(!visit[i]) {
     subConnectBranch++;
     visit[i] = true;
     dfs(visit, i, arr, ocp);
    }
   }
   System.out.println(subConnectBranch-1);
  }
 }
 public static void dfs(boolean visit[], int id, City[] arr, int ocp) {
  City p = arr[id];
  while(p.next != null) {
   p = p.next;
   if(p.id!=ocp && !visit[p.id]) {
    visit[p.id] = true;
    dfs(visit, p.id, arr, ocp);
   }
  }
 }
 static class City{
  int id;
  City next;
  public City(int id){
   this.id = id;
  }
 }
}