CodeForces25DRoadsnotonlyinBerland(并查集题目)

本题为并查集题目&＃xff0c;个人觉得本题的答案并不唯一
题目的大意为&＃xff1a;为了方便沟通任一两地之间&＃xff0c;所以删除一条路的时候沟通另外一条路&＃xff08;一天只能进行一次&＃xff09;&＃xff0c;并且让花费的天数尽可能的少&＃xff0c;所以在这里就得用并查集对是否成环进行判断。对成环的路断开&＃xff0c;然后在端点连接另外一条与上一个环没有交点的路线&＃xff0c;渣渣可能说的不太详细&＃xff0c;各大神结合代码和题目样例再进行思考吧&＃xff0c;就说到这里&＃xff0c;下面附上AC代码。

这里写代码片#include
#include
#include
using namespace std;int pre[1005];
struct Node{int u,v;
}a[1005];
int find(int x){if(x!&＃61;pre[x]){pre[x]&＃61;find(pre[x]);}return pre[x];
}
void join(int x,int y){int i&＃61;find(x);int j&＃61;find(y);pre[i]&＃61;j;
}
int main(){int n;while(~scanf("%d",&n)){int cnt&＃61;0;for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;){pre[i]&＃61;i;}for(int i&＃61;0;i1;i&＃43;&＃43;){int x,y;scanf("%d %d",&x,&y);if(find(x)&＃61;&＃61;find(y)){a[cnt].u&＃61;x;a[cnt].v&＃61;y;cnt&＃43;&＃43;;}else{join(x,y);}}printf("%d\n",cnt);int sum&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){if(find(i)!&＃61;find(j)){printf("%d %d %d %d\n",a[sum].u,a[sum].v,i,j);join(i,j);sum&＃43;&＃43;;if(sum&＃61;&＃61;cnt) break;}}}}
}