D. Johnny and Contribution(贪心)

D. Johnny and Contribution(贪心)

思路:贪心,显然可以知道要从小到大涂,首先我们把为期望颜色为111的都涂掉,然后对每个uuu判断一下相邻结点vvv的期望颜色是否也为111,如果是vvv的期望颜色++++++.

依次类推。因为是 从小开始涂的,所以保证当前比uuu颜色小的都涂了。所以就可以直接判断了。只要当前结点uuu的期望颜色不是原来的颜色iii就可以直接返回1-1−1了。注意初始化一下期望颜色为111即可。

#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;
} 
上一篇:redis


下一篇:Js遍历对象总结