P10179 水影若深蓝题目背景帆帆爱明日方舟更爱水月和深蓝之树。但在龙年他想构建一棵独属于他的深蓝之树。题目描述在梦里在朦胧的水影中帆帆看见了这棵只属于他的深蓝之树。当一切梦沉寂他却遗忘了所有只记得树上有nnn个结点。真的吗似乎并没有有mmm件事情他一直牢记着第iii件事情是节点uiu_iui​和viv_ivi​在这棵深蓝之树上唯一的不重复经过某个点的路径恰好有两条边。那么你能否帮助帆帆想起来这棵深蓝之树的样子呢如果有多个可能的你只需要输出任意一种。当然帆帆也是会磨损的因此当你发现无论如何都找不到满足帆帆这mmm件事情的深蓝之树时你需要报告无解。输入格式本题有多组数据。第一行一个正整数TTT表示数据组数。对于每组数据第一行两个非负整数n,mn,mn,m表示树上的点数和帆帆记忆中事件个数。接下来mmm行每行两个正整数ui,viu_i,v_iui​,vi​表示一个事件。输出格式对于每组数据若不存在符合条件的树输出No。否则第一行输出Yes接下来n−1n-1n−1行输出n−1n-1n−1对正整数(u,v)(u,v)(u,v)表示你给出的树上的n−1n-1n−1条边。本题采用special judge评测也就是说如果有多种可能的答案你可以输出任意一种。输入输出样例 #1输入 #12 4 2 1 2 3 4 3 3 1 2 2 3 3 1输出 #1Yes 1 3 2 4 2 3 No说明/提示样例111解释对于第一组数据不难验证给出的树符合条件。对于第二组数据可以证明不存在符合条件的树。测试点约束对于100%100\%100%的数据1≤T≤1051\le T\le 10^51≤T≤105n≥2n\ge 2n≥2m≥0m\ge 0m≥01≤∑n≤3×1051\le \sum n\le 3\times 10^51≤∑n≤3×1050≤∑m≤3×1050\le \sum m\le 3\times 10^50≤∑m≤3×1051≤ui,vi≤n1\le u_i,v_i\le n1≤ui​,vi​≤nui≠viu_i\neq v_iui​vi​。本题采用捆绑测试。子任务编号特殊限制分值Subtask #1∑n,∑m≤9\sum n,\sum m\le 9∑n,∑m≤9101010Subtask #2∑n,∑m≤50\sum n,\sum m\le 50∑n,∑m≤50101010Subtask #3∑n,∑m≤5000\sum n,\sum m\le 5000∑n,∑m≤5000101010Subtask #4viui1v_iu_i1vi​ui​1101010Subtask #5ui1u_i1ui​1101010Subtask #6ui≠1,vi≠1u_i\neq 1,v_i\neq 1ui​1,vi​1101010Subtask #7T1T1T1101010Subtask #8无303030C实现#includebits/stdc.husingnamespacestd;constintN1e510;intT,n,m,fa[N];inlineintgetfa(intx){returnxfa[x]?x:fa[x]getfa(fa[x]);}intmain(){scanf(%d,T);while(T--){scanf(%d%d,n,m);for(inti1;in;i)fa[i]i;for(inti1,x,y;im;i){scanf(%d%d,x,y);assert(x!y);xgetfa(x);ygetfa(y);fa[x]y;}intcnt0;intp[2];for(inti1;in;i){if(getfa(i)!i)continue;if(cnt2)p[cnt]i;cnt;}if(cnt1n1){puts(No);continue;}if(cnt1n1){puts(Yes);continue;}puts(Yes);printf(%d %d\n,p[0],p[1]);for(inti1;in;i){if(ip[0]||ip[1])continue;if(getfa(i)p[0])printf(%d %d\n,i,p[1]);elseprintf(%d %d\n,i,p[0]);}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容