题目解析
给定一个国家有n个城市，m条路
再给定k个攻击城市的顺序 依次攻击
-
每次攻击完 判断这个城市会不会改变整个国家的连通性
-
改变:
Red Alert: City k is lost!其中k是该城市的编号 -
不改变:
City k is lost.其中k是该城市的编号
-
-
如果国家失去最后一个城市了就输出
Game Over.
（注：如果城市被攻占了， 那么接下来这个点就相当于删除掉了）
解题思路
题目给定一个无向图（因为不能保证），需要每次判断删除的 点是否会将原有的连通图分成多个图
首先判断一个连通的图中删除一个点是否分为多个连通图
如何实现呢？
是不是可以搜索 或者 并查集呢
搜索： 遍历节点统计节点堆的数量
并查集： 将每个节点堆都用一个父节点代替， 统计父节点的数量
如何判断删除一个点是否改变连通性？
-
首先知道他们俩统计的是什么
-
bfs：删除点后所有节点群数
-
并查集： 所有节点的宗族节点为本身的数
- 那如此的话 并查集统计数量时会比bfs 多统计删除的节点数
-
-
判断是否改变
-
bfs：删除当前节点时统计的数量比没删除之前的多
-
并查集：删除当前节点是统计的数量比没删除之前的多2
- bfs的应该很简单吧 能直接看懂为啥多就能改变
- 并查集呢 我们看两个例子即可
-
-
只多1为啥不行？
- 无论删除节点1还是节点2，删除那个节点的话，节点群数从1个变为2个，没有改变剩余城市的连通性
-
如果删除节点2呢？节点群数从1个变为3个，改变了剩余城市的连通性
其他的没啥需要注意的
然后就直接开干吧
代码
bfs
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int n, m;
static boolean map[][], vis[], del[];
static void bfs(int u)
{
ArrayList<Integer> ar = new ArrayList<Integer>();
ar.add(u);
while (ar.size() != 0)
{
int t = ar.remove(0);
vis[t] = true;
for (int i = 0; i < n; i++)
{
// 当前节点没有遍历过 并且 没有删除 且 当前能到达
if (!vis[i] && !del[i] && map[t][i])
ar.add(i);
}
}
}
// 查询有多少个节点群
static int cnt()
{
int ans = 0;
for (int i = 0; i < n; i++)
{
// 当前节点没有遍历过 并且 没有删除
if (!vis[i] && !del[i])
{
bfs(i);
ans++;
}
}
return ans;
}
public static void main(String[] args) throws IOException
{
n = ini();
m = ini();
map = new boolean[n][n]; // 存图
vis = new boolean[n]; // 节点是否遍历过
del = new boolean[n]; // 节点是否被删除
while (m-- > 0)
{
int a = ini(), b = ini();
map[a][b] = map[b][a] = true; // 两地连通
}
int cnt1 = cnt();
int k = ini();
for (int i = 1; i <= k; i ++)
{
int x = ini();
del[x] = true; // 这个点删除掉
vis = new boolean[n];
int cnt2 = cnt();
// 如果删除当前节点后连通分支数比之前小或者相等,则说明没改变图的连通性,否则则改变了
if (cnt1 >= cnt2)
out.printf("City %d is lost.\n", x);
else
out.printf("Red Alert: City %d is lost!\n", x);
cnt1 = cnt2; // 更新节点群数
}
// 删除了节点数个的话 就是国家没有一个城市了
if (k == n)
out.println("Game Over.");
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
}
可能会超时 但是多交两下就可以了
并查集
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int n, m;
static int fa[];
static boolean map[][];
static void fill()
{
for (int i = 0; i < n; i++)
fa[i] = i;
}
static int find(int x)
{
if (fa[x] != x)
fa[x] = find(fa[x]);
return fa[x];
}
// 查询有多少个节点群的父节点个数
static int cnt()
{
int ans = 0;
for (int i = 0; i < n; i++)
{
if (fa[i] == i)
ans++;
}
return ans;
}
public static void main(String[] args) throws IOException
{
n = ini();
m = ini();
fa = new int[n]; // 存当前节点的父节点
map = new boolean[n][n]; // 存图
fill();
while (m-- > 0)
{
int a = ini(), b = ini();
fa[find(a)] = find(b); // a的祖宗节点 变为 b的祖宗节点
map[a][b] = map[b][a] = true; // 两地连通
}
int cnt1 = cnt();
int k = ini();
while (k-- > 0)
{
int x = ini();
// 删除两地的连通
for (int i = 0; i < n; i++)
map[i][x] = map[x][i] = false;
fill();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// 有路就认爹
if (map[i][j])
fa[find(i)] = find(j);
}
}
int cnt2 = cnt();
// 注： 并查集这里的话 删除只是将这个点不再与其他点联通。 这个就自己为一个点了
if (cnt1 >= cnt2 - 1)
out.printf("City %d is lost.\n", x);
else
out.printf("Red Alert: City %d is lost!\n", x);
cnt1 = cnt2; // 更新节点群数
}
// 最后的节点群数 等于 节点数的话 就是国家没有一个城市了
if (cnt1 == n)
out.println("Game Over.");
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
}
java会超时2和4 c++则不会
ArrayList
ArrayList
LinkedList
arraylist和linkedlist的区别
arraylist和linkedlist的区别