题意:
图问题,意思是在一个无向图中,以城市为顶点,城市之间有高速公路连接着,战争爆发,如果一个城市被敌人占领了,其他城市之间需要用高速公路运送物资,至少要修几条公路。
解题思路:
城市被占领后,本来连通(不一定)着的城市可能变得不再连通了,转化为求连通子图个数问题,即:这些城市之间形成了多少个连通子图(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;
}
}
}
|