wp系统网站如何做seo/在线代理浏览网页

---

题目解读

给定一个无向图V，询问是否可以用K种颜色为V中每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色

输入格式

第一行给出V,E,K，
分别代表无向图的顶点，边数，以及颜色数。
顶点和颜色都从1到V编号。
随后E行,每行表示一条边的两个端点。
随后给出正整数N，表示检查颜色分配方案的个数
最后N行，每行给出V个顶点的颜色
注意这个这里给出的V个顶点的颜色数量大于K,那么可直接输出No

输出格式

对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

思路

存好图之后对每一个没有遍历过的顶点进行遍历

Ac CODE

#include<bits/stdc++.h>using namespace std;const int N = 510;
int g[N][N];//邻接矩阵存图 
int color[N];//标记颜色
bool used[N];//标记数组,标记当前点是否遍历过 
int v,e,k,n;bool dfs(int u){//标记遍历过 used[u]=1;for(int i=1; i<=v; i++){//如果当前两个顶点有边 if(g[u][i]==1){//判断这两个顶点的颜色是否相同 if(color[u] == color[i]){cout<<"No\n";return 0;}//如果相连的边没有被遍历过,那么遍历 if(used[i]==0){//只要有一个不合法,那么就返回false if(dfs(i)==0)return 0;}}}//如果遍历完所有与该顶点相连的边都合法,那么返回1 return 1;
}int main(){//顶点点数，边数,颜色数。cin >> v >> e >> k;for(int i=0; i<e; i++){int x,y;cin >> x >> y;g[x][y]=g[y][x]=1;}cin >> n;//颜色分配方案个数 while(n--){//多组数据,要给used数组进行初始化赋值 memset(used,0,sizeof used);map<int,bool> temp;//遍历n个顶点for(int i=1; i<=v; i++){//读入当前顶点的颜色 cin>>color[i];//如果当前颜色找不到,那么存储进入map; if(temp.count(color[i])==0)temp[color[i]]=1;}//如果颜色总数大于k,那么直接就不合法 if(temp.size() != k){cout<<"No\n";continue;}else{for(int i=1; i<=v; i++){//如果当前顶点没有遍历过,那么从当前顶点开始遍历 if(used[i] == 0){if(dfs(i)==0)break;}if(i==v)cout<<"Yes\n";}}}return 0;
}

参考

B站up主–一天能吃五顿饭

---

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇

---