题目链接
给定一个无向连通图,然后去掉其中某个点,问是否还连通,如果不连通,需要最少几条路使其连通;
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { static int[][] g; static boolean[] visited; static int n; public static void dfs(int index){ visited[index] = true; for(int i=1; i<n; ++i){ if(!visited[i] && g[index][i] == 1){ dfs(i); } } } public static void main(String[] args) throws IOException { StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); sc.nextToken(); n = (int)sc.nval + 1; sc.nextToken(); int m = (int)sc.nval; sc.nextToken(); int k = (int)sc.nval; g = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < m; i++) { sc.nextToken(); int x = (int)sc.nval; sc.nextToken(); int y = (int)sc.nval; g[x][y] = 1; g[y][x] = 1; } for (int i = 0; i < k; i++) { Arrays.fill(visited, false); sc.nextToken(); int z = (int)sc.nval; visited[z] = true; int count = 0; for (int j = 1; j < n; j++) { if(!visited[j]){ count++; dfs(j); } } System.out.println(count-1); } } }