题目解析
给定一个无向图
再给你几组颜色方案
判断这几种颜色方案是否符合
符合条件：相邻两个点颜色不能相同
解题思路
先存储图的信息
然后判断输入的颜色数是否符合
最后依次遍历存储的图
看是否有相邻的节点颜色相同
其实可以用链表存储的，但是还不如对象数组方便呢
所以直接对象数组存储了
代码
import java.io.*;
import java.util.*;
public class Main
{
static int N = (int) 1e6;
static edge tu[] = new edge[N + 10]; // 存储图的信息
static int V[] = new int[N + 10]; // 存储颜色分配的方案
static int v, e, k;
static boolean is()
{
for (int i = 1; i <= e; i++)
{
int x = tu[i].x, y = tu[i].y;
if (V[x] == V[y]) // 判断两个端点的颜色是不是一样的
return false;
}
return true;
}
public static void main(String[] args) throws IOException
{
v = ini();
e = ini();
k = ini();
for (int i = 1; i <= e; i++)
{
int a = ini(), b = ini();
tu[i] = new edge(a, b);
}
int n = ini();
while (n-- > 0)
{
TreeSet<Integer> tr = new TreeSet<Integer>(); // 存储颜色种类
for (int i = 1; i <= v; i++)
{
V[i] = ini();
tr.add(V[i]);
}
if (tr.size() != k) // 颜色种类是否颜色数相同
out.println("No");
else
out.println(is() ? "Yes" : "No");
}
out.flush();
out.close();
}
static class edge
{
int x, y;
public edge(int x, int y)
{
this.x = x;
this.y = y;
}
}
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;
}
}