D. Johnny and Contribution(贪心)
思路:贪心,显然可以知道要从小到大涂,首先我们把为期望颜色为1的都涂掉,然后对每个u判断一下相邻结点v的期望颜色是否也为1,如果是v的期望颜色++.
依次类推。因为是 从小开始涂的,所以保证当前比u颜色小的都涂了。所以就可以直接判断了。只要当前结点u的期望颜色不是原来的颜色i就可以直接返回−1了。注意初始化一下期望颜色为1即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
#define mst(a) memset(a,0,sizeof a)
int num[N],n,m;
vector<int>e[N],ans,col[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++){
int c;
scanf("%d",&c);
col[c].push_back(i);
num[i]=1;
}
for(int i=1;i<=n;i++){
for(auto u:col[i]){
if(num[u]!=i) puts("-1"),exit(0);
for(auto v:e[u])
if(num[v]==i) num[v]++;
ans.push_back(u);
}
}
for(auto i:ans) printf("%d ",i);
return 0;
}