题目大意：有n篇博客，看着n个点，有m条边，每个点都可以赋予一个值，将所有直连边的点放入一个集合中，这个点的权值就是集合中没有的最小正整数。比如，有三条边a b ，a c ，a d，b的值是1 c的是3 d的是5 那么a就得是2； 现在给你一个所有点的期望赋值，问能不能有一种赋值顺序可以使所有点达成这个期望的权值。
解题思路：贪心策略，先所有点赋值初始化为1。从期望是1的点开始赋值，然后将这个点所有相连的点v，如果v的值和当前点u相同就将v的值+1。如果出现一个点的当前值不是期望值则说明无法达成。由于我们是从1开始递增期望的赋值所有这个策略的正确性可以得到保证。
code
#include <iostream> #include <string> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <functional> #include <map> #include <set> #include <stack> #include <vector> #include <unordered_set> #define FT(a, b) memset(a, b, sizeof(a)) #define FAT(a) memset(a, 0, sizeof(a)) using namespace std; typedef long long ll; const int M = 1e6 + 100; const int N = 5e5 + 100; const int INF = 0x3f3f3f3f; const int mod = 998244353; const double PI = 3.1415926535; int e[M], ne[M], h[N], idx, n, m; int vis[N]; vector<int> v[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int main() { #ifdef ONLINE_JUDGE #else freopen("D:\\code\\c++\\in.txt", "r", stdin); #endif FAT(vis); FT(h, -1); idx = 0; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b, a); } int maxn = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); maxn = max(maxn, x); v[x].push_back(i); } bool flag = 0; for (int i = 1; i <= maxn; i++) { if (flag) break; for (auto it : v[i]) { if (vis[it] != i-1) { flag = 1; break; } else { for (int j = h[it]; ~j; j = ne[j]) { int k = e[j]; if (vis[k] == i-1) vis[k]++; } } } } if (flag) puts("-1"); else { for (int i = 1; i <= maxn; i++) { for (auto it : v[i]) printf("%d ", it); } puts(""); } return 0; }
Codeforces Round #647 (Div. 2) D
原文：https://www.cnblogs.com/ignorance/p/13054690.html