本文主要是介绍【蓝桥杯】着色问题 DFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.着色问题
1.问题描述
存在一个无向图，要求给图中的点涂色，并且有线连接的点之间不能是同一种颜色。
2.输入格式
第一行为两个正整数 n , m ( 0 < n , m < 100 ) 分别表示录入的图的点数以及边数
第二行为一个正整数num，表示能用的颜色数（每种颜色用一个正整数来表示，从 1 开始逐渐增 1 的正整数）
之后为m行，每行两个数x，y，表示点x和y之间有一条边（点从 1 开始，为逐渐增 1 的正整数）
3.输出格式
输出在当前情形下的上色方案的数量
4.问题分析
4.1 判断位置为pos的点是否能够涂上代号为x的颜色
4.2 dfs搜索
对图进行遍历，可以使用深度优先搜索。对于上色方案，我们首先考虑点1上什么颜色（遍历所有的颜色），再考虑点2，……。由于前面点的限制，后面的点的上色会受限。
此时每形成一种方案就需要进行回退。
5.代码实现
//着色问题
#include <iostream>using namespace std;const int N=110;bool map[N][N]={false};
int color[N]={0};//color[i]=x 表示第i个点涂上代号为x的颜色
int n,m,num,ans=0;bool judge(int pos,int x){for(int i=1;i<=n;i++)if(map[pos][i]&&color[i]==x)return false;return true;
}void dfs(int pos){if(pos>n){ans++;return;}for(int i=1;i<=num;i++){if(judge(pos, i)){color[pos]=i;dfs(pos+1);color[pos]=0;}}
}int main(int argc, const char * argv[]) {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int x,y;cin>>n>>m>>num;for(int i=0;i<m;i++){cin>>x>>y;map[x][y]=map[y][x]=true;}dfs(1);cout<<ans<<'\n';return 0;
}二.分考场
1.问题描述
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求至少需要分几个考场才能满足条件。
2.输入描述
第一行，一个整数n()，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 () 表示第a个人与第b个人认识。
3.输出描述
输出一行一个整数，表示最少分几个考场。
4.问题分析
dfs的参数问题，每次需要知道安排的是第几个学生，当前已经开辟了多少个考场。
剪枝，如果当前开辟考场的数目已经大于了ans，那么直接return。
已经安排好所有的学生，则ans=roomNum。
遍历所有的教室，对每一个教室里的学生再进行遍历，判断当前正在安排的学生是否和教室里已有的学生认识。
若没有人认识当前学生，则将该学生放进该教室，并继续安排下一个学生，回退时需要将该学生从教室里清除。
若当前教室都不可用，则新开辟一件教室给该学生，并继续安排下一个学生，回退时需要将该学生从教室里清除。
5.代码实现
//分考场
#include <iostream>
#include <vector>
using namespace std;const int N=110;bool map[N][N]={false};
int n,m,ans=N;//ans需要赋一个初始值
vector <int> classroom[N];void dfs(int num,int roomNum){if(roomNum>=ans)//剪枝return;if(num>n){//已经安排好所有的学生ans=roomNum;return;}for(int i=1;i<=roomNum;i++){//遍历所有教室int j=0,len=(int)classroom[i].size();for(j=0;j<len;j++){//检测当前教室中是否有人与当前被安排的学生认识if(map[num][classroom[i][j]])break;}if(j==len){//没有学生与当前被安排的学生认识，当前被安排的学生可以被放进该教室classroom[i].push_back(num);//当前教室插入该学生dfs(num+1,roomNum);//继续安排下一个学生classroom[i].pop_back();//回退时将当前学生从该教室清除}}classroom[roomNum+1].push_back(num);//开一间新教室给当前学生dfs(num+1,roomNum+1);//继续安排下一个学生classroom[roomNum+1].pop_back();//回退时将当前学生从该教室清除
}int main(int argc, const char * argv[]) {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int a,b;cin>>n>>m;for(int i=0;i<m;i++){cin>>a>>b;map[a][b]=map[b][a]=true;}dfs(1,0);cout<<ans<<'\n';return 0;
}
这篇关于【蓝桥杯】着色问题 DFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
