PAT甲级 1154 Vertex Coloring（25）

这道25分题闹麻了，大水题，根本不用建图+dfs，直接存边比较就行了。但是java会超时，c++可以过。

1170 Safari Park（25） 跟这题几乎一个模子。

#include <bits/stdc++.h>
using namespace std;
int M, N, K;
vector<vector<int>> edges;

int getColorTypes(int* colors, int n) {
	set<int> colorSet;
	for (int i = 0; i < n; ++i) {
		colorSet.insert(colors[i]);
	}
	return colorSet.size();
}

bool check(int* colors) {
	for (auto v: edges) {
		if (colors[v[0]] == colors[v[1]]) {
			return false;
		}
	}
	return true;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		vector<int> v(2);
		cin >> v[0] >> v[1];
		edges.emplace_back(v);
	}
	cin >> K;
	for (int i = 0; i < K; ++i) {
		int *colors = new int[N];
		for (int j = 0; j < N; ++j) {
			cin >> colors[j];
		}
		if (check(colors)) {
            int colorTypes = getColorTypes(colors, N);
			printf("%d-coloring\n", colorTypes);
		} else {
			cout << "No" << endl;
		}
	}
}