P7428 [THUPC 2017] 母亲节的礼物
题目描述
小 B 喜欢图，尤其是边数不太多的无向简单图。
母亲节快到了，小 B 在纸上画了一张有nnn个节点、mmm条边的无向简单图（即，不存在重边、自环），保证每个点只和最多777个点相邻。接着，他想用444种不同的颜色给图中的节点进行染色，作为妈妈的母亲节礼物送给她。
小 B 希望染色之后的图尽量漂亮，他觉得相同颜色的点连成一片不好看。所以，他希望能给每对相邻的节点染上不同的颜色。遗憾的是，小 B 很快发现，在有些图中，这是不可能做到的。他不得不降低要求：每个点相邻的点中，至多有一个点和它的颜色相同。
限制条件放松了，问题也就变得简单了；但是小 B 忙着做大作业，所以来找你帮忙。现在，请你告诉小 B，是否能给图中每个点染上一个恰当的颜色，恰好满足小 B 的要求？如果可以，请你给他指出一种染色方案；否则，只好残忍地告诉小 B：impossible。
输入格式
输入有多组数据，第一行一个整数TTT（1≤T≤101\le T\le 101≤T≤10） ，表示数据组数。
对于每组数据：
第一行两个整数n,mn,mn,m（1≤n≤25000,1≤m≤1051\le n\le 25000,1\le m\le 10^51≤n≤25000,1≤m≤105），分别表示图的点数和边数（约定点从111开始标号）。
接下来mmm行，每行两个整数x,yx,yx,y（1≤x,y≤n1\le x,y\le n1≤x,y≤n），描述图中的一条边，保证不存在重边、自环。
保证在一个输入文件中，有∑n≤200000,∑m≤800000\sum n\le 200000,\sum m\le 800000∑n≤200000,∑m≤800000。
输出格式
我们用小写英文字母a、b、c、d给四种不同的颜色标号。
对于每组数据：
- 如果有解，输出一行一个长度为nnn的字符串SSS，其中SiS_iSi表示你给第iii个点染上的颜色（下标从111开始）；
- 否则，输出 impossible。
输入输出样例 #1
输入 #1
1 8 28 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 3 2 4 2 5 2 6 2 7 2 8 3 4 3 5 3 6 3 7 3 8 4 5 4 6 4 7 4 8 5 6 5 7 5 8 6 7 6 8 7 8输出 #1
abcdabcd说明/提示
版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。
C++实现
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;structnode{intv,nxt;}e[200010];intt,n,m,tot;intcolor[25010],head[25010],d[25010],num[25010];queue<int>q;intread(){charc=getchar();intx=0;while(!isdigit(c))c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();returnx;}voidadd(intu,intv){e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot;}signedmain(){srand(time(NULL));t=read();while(t--){n=read(),m=read();tot=0;for(inti=1;i<=n;i++)color[i]=-1,d[i]=0,head[i]=0;for(inti=1,u,v;i<=m;i++)u=read(),v=read(),add(u,v),add(v,u);for(inti=1;i<=n;i++)color[i]=rand()%4;while(!q.empty())q.pop();for(intx=1;x<=n;x++){for(inti=head[x];i;i=e[i].nxt)if(color[x]==color[e[i].v])d[x]++;if(d[x]>1)q.push(x);}while(!q.empty()){intx=q.front();q.pop();for(inti=head[x];i;i=e[i].nxt)if(color[x]==color[e[i].v])d[x]--,d[e[i].v]--;for(inti=0;i<=3;i++)num[i]=0;for(inti=head[x];i;i=e[i].nxt)num[color[e[i].v]]++;inttt=8,cl;for(inti=0;i<=3;i++)if(tt>num[i])tt=num[i],cl=i;color[x]=cl;for(inti=head[x];i;i=e[i].nxt){if(color[x]==color[e[i].v])d[x]++,d[e[i].v]++;if(d[e[i].v]>1)q.push(e[i].v);}}for(inti=1;i<=n;i++)printf("%c",'a'+color[i]);puts("");}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
