网站建设上机实验心得,南京app制作开发公司,买一个成品网站多少钱,贵州企业网站建设价格题意#xff1a;输入n个点m条边的联通图#xff0c;n为奇数#xff0c;设k为最小的奇数#xff0c;使得每个点的度数不超过k#xff0c;要求把节点都涂上颜色#xff0c;使得相邻节点颜色不一样。 思路#xff1a;dfs。k的值为奇数#xff0c;所以k为节点最大度数…题意输入n个点m条边的联通图n为奇数设k为最小的奇数使得每个点的度数不超过k要求把节点都涂上颜色使得相邻节点颜色不一样。 思路dfs。k的值为奇数所以k为节点最大度数1。从当前节点往下找如果下边的节点没有染色就把当前节点染色继续下找。
code #include iostream
#include cstdio
#include cmath
#include algorithm
#include cstring
#include sstream
#include string
#include vector
#include list
#include queue
#include stack
#include map
#include set
#include bitsetusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;const int INF0x3fffffff;
const int inf-INF;
const int N10005;
const int M2005;
const int mod1000000007;
const double piacos(-1.0);#define cls(x,c) memset(x,c,sizeof(x))
#define cpy(x,a) memcpy(x,a,sizeof(a))
#define fr(i,s,n) for (int is;in;i)
#define lson l,m,rt1
#define rson m1,r,rt1|1
#define lrt rt1
#define rrt rt1|1
#define middle int m(rl)1
#define lowbit(x) (x-x)
#define pii pairint,int
#define mk make_pair
#define IN freopen(in.txt,r,stdin);
#define OUT freopen(out.txt,w,stdout);int s[N],vis[N];
vectorintg[N];
int k,n,m;void dfs(int u)
{cls(vis,0);vectorintne;for (int i0;ig[u].size();i){int vg[u][i];if (s[v]) vis[s[v]]1;else ne.push_back(v);}for (int i1;ik;i){if (!vis[i]) {s[u]i;break;}}for (int i0;ine.size();i){if (!s[ne[i]]) dfs(ne[i]);}
}
int main()
{int a,b,ca0;while (~scanf(%d %d,n,m)){if (ca) puts();for (int i0;in;i) g[i].clear();for (int i0;im;i){scanf(%d %d,a,b);g[a-1].push_back(b-1);g[b-1].push_back(a-1);}cls(s,0);k-1;for (int i0;in;i) kmax(k,(int)g[i].size());if (k%20) k;printf(%d\n,k);dfs(0);for (int i0;in;i) printf(%d\n,s[i]);}
}
