打卡信奥刷题（3179）用C++实现信奥题 P8014 [COCI 2013/2014 #4] SUMO

P8014 [COCI 2013/2014 #4] SUMO题目描述有N NN个选手参加M MM场1 11对1 11的比赛比赛顺序已经定好。现在让你将这些选手分成2 22队使选手尽可能晚地碰到同队的选手。输出最优方案下第一次有选手碰到同队的的选手的比赛序号。输入格式第一行一个正整数N NN表示有N NN个选手第二行一个正整数M MM表示有M MM场比赛接下来M MM行每行两个正整数A i A_iAi​和B i B_iBi​表示序号为i ii的比赛参与的选手是序号为A i A_iAi​和B i B_iBi​的两位选手。输出格式一行一个正整数表示最优分队方案下第一次有选手碰到同队的的选手的比赛序号。输入输出样例 #1输入 #15 5 1 2 2 3 3 4 4 5 5 1输出 #15输入输出样例 #2输入 #26 8 1 2 3 4 5 6 1 3 1 6 4 5 2 4 2 6输出 #26说明/提示【样例解释 #1】[ 1 , 3 , 5 ] [1,3,5][1,3,5]一队[ 2 , 4 ] [2,4][2,4]一队。可以证明这是最优方案。【数据范围】对于100 % 100\%100%的数据1 ≤ A i , B i ≤ N ≤ 10 5 1\le A_i,B_i\le N\le 10^51≤Ai​,Bi​≤N≤1051 ≤ M ≤ 3 × 10 5 1\le M\le 3\times 10^51≤M≤3×105。【来源】本题分值按 COCI 原题设置满分100 100100。题目译自 COCI2013-2014 CONTEST #4T3 SUMO。C实现#includeiostreamusingnamespacestd;intf[100001]{0};intd[100001]{0};intfind(intx){if(f[x]x)returnx;returnf[x]find(f[x]);}voidhb(intx,inty){f[x]y;}intmain(){intn,m;cinnm;for(inti1;in;i)f[i]i;//初始化 father 数组。for(inti1;im;i){intx,y;cinx;ciny;intxxfind(x);//这里我提前查找了能为后面节约一点点时间虽然就一点点。intyyfind(y);if(xxyy){//判断是否找到答案即正在 PK 的两人是否已经是同一队。coutiendl;break;}if(find(d[x])!yyd[x]!0){//d[x]!0 是判断是否还是初始状态。hb(find(d[x]),yy);}if(find(d[y])!xxd[y]!0){hb(find(d[y]),xx);}d[x]yy;//标记为敌人。d[y]xx;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容