打卡信奥刷题（3126）用C++实现信奥题 P7428 [THUPC 2017] 母亲节的礼物

P7428 [THUPC 2017] 母亲节的礼物题目描述小 B 喜欢图尤其是边数不太多的无向简单图。母亲节快到了小 B 在纸上画了一张有nnn个节点、mmm条边的无向简单图即不存在重边、自环保证每个点只和最多777个点相邻。接着他想用444种不同的颜色给图中的节点进行染色作为妈妈的母亲节礼物送给她。小 B 希望染色之后的图尽量漂亮他觉得相同颜色的点连成一片不好看。所以他希望能给每对相邻的节点染上不同的颜色。遗憾的是小 B 很快发现在有些图中这是不可能做到的。他不得不降低要求每个点相邻的点中至多有一个点和它的颜色相同。限制条件放松了问题也就变得简单了但是小 B 忙着做大作业所以来找你帮忙。现在请你告诉小 B是否能给图中每个点染上一个恰当的颜色恰好满足小 B 的要求如果可以请你给他指出一种染色方案否则只好残忍地告诉小 Bimpossible。输入格式输入有多组数据第一行一个整数TTT1≤T≤101\le T\le 101≤T≤10 表示数据组数。对于每组数据第一行两个整数n,mn,mn,m1≤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,y1≤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输入 #11 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输出 #1abcdabcd说明/提示版权信息来自 THUPCTHU Programming Contest清华大学程序设计竞赛2017。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;structnode{intv,nxt;}e[200010];intt,n,m,tot;intcolor[25010],head[25010],d[25010],num[25010];queueintq;intread(){charcgetchar();intx0;while(!isdigit(c))cgetchar();while(isdigit(c))x(x1)(x3)(c^48),cgetchar();returnx;}voidadd(intu,intv){e[tot].vv,e[tot].nxthead[u],head[u]tot;}signedmain(){srand(time(NULL));tread();while(t--){nread(),mread();tot0;for(inti1;in;i)color[i]-1,d[i]0,head[i]0;for(inti1,u,v;im;i)uread(),vread(),add(u,v),add(v,u);for(inti1;in;i)color[i]rand()%4;while(!q.empty())q.pop();for(intx1;xn;x){for(intihead[x];i;ie[i].nxt)if(color[x]color[e[i].v])d[x];if(d[x]1)q.push(x);}while(!q.empty()){intxq.front();q.pop();for(intihead[x];i;ie[i].nxt)if(color[x]color[e[i].v])d[x]--,d[e[i].v]--;for(inti0;i3;i)num[i]0;for(intihead[x];i;ie[i].nxt)num[color[e[i].v]];inttt8,cl;for(inti0;i3;i)if(ttnum[i])ttnum[i],cli;color[x]cl;for(intihead[x];i;ie[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(inti1;in;i)printf(%c,acolor[i]);puts();}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容