题目解析
给定一个无向图，再给你k组进攻路线，判断这k组进攻路线是否可行
解题思路
暴力判断即可
首先如何判断当前城市是否孤立无援呢
也就是当前城市没被攻击，且相邻城市都被攻击了，这样子该城市就是孤立无援的城市
最后就是用无向图存储，for循环暴力去判断当前方案是否可行即可
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e4;
static ArrayList<Integer> map[] = new ArrayList[N + 10]; // 存储城市
static boolean vis[] = new boolean[N + 10]; // 标记当前城市是否被攻击
static int n, m;
static boolean check()
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < map[i].size(); j++)
{
// 当前城市没有被攻击且相邻国家也没有被攻击
if (!vis[i] && !vis[map[i].get(j)])
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException
{
n = ini();
m = ini();
for (int i = 1; i <= n; i++)
map[i] = new ArrayList<Integer>();
while (m-- > 0)
{
int a = ini(), b = ini();
map[a].add(b);
map[b].add(a);
}
int k = ini();
while (k-- > 0)
{
int np = ini();
vis = new boolean[n + 10];
while (np-- > 0)
{
int v = ini();
vis[v] = true; // 当前城市被攻打了
}
out.println(check() ? "YES" : "NO");
}
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;
}
}