Codeforces 25D-Roads not only in Berland 并查集

65 阅读 0 评论 43 点赞

我是靠谱客的博主凶狠火，最近开发中收集的这篇文章主要介绍Codeforces 25D-Roads not only in Berland 并查集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Roads not only in Berland

Berland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roads so that from each city of Berland and neighboring countries it became possible to reach all the others. There are n cities in Berland and neighboring countries in total and exactly n - 1 two-way roads. Because of the recent financial crisis, the Berland Government is strongly pressed for money, so to build a new road it has to close some of the existing ones. Every day it is possible to close one existing road and immediately build a new one. Your task is to determine how many days would be needed to rebuild roads so that from each city it became possible to reach all the others, and to draw a plan of closure of old roads and building of new ones.

Input

The first line contains integer n (2 ≤ n ≤ 1000) — amount of cities in Berland and neighboring countries. Next n - 1 lines contain the description of roads. Each road is described by two space-separated integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — pair of cities, which the road connects. It can't be more than one road between a pair of cities. No road connects the city with itself.

Output

Output the answer, number t — what is the least amount of days needed to rebuild roads so that from each city it became possible to reach all the others. Then outputt lines — the plan of closure of old roads and building of new ones. Each line should describe one day in the format i j u v — it means that road between cities iand j became closed and a new road between cities u and v is built. Cities are numbered from 1. If the answer is not unique, output any.

Example

Input

2
1 2

Output

Input

Output

1
3 1 3 7

题目分析：有n个城市n-1条公路，现在需要让所有的城市都可以互相到达，我们可以拆出一条公路然后再从新建一条新的公路。问需要拆多少条公路，并将拆的和建的都输出。

这个题简单的说就是给一个n个顶点n-1条边的无向图，去掉图中的环并且将不联通的两部分连上。思路是用并查集判断是否有环，并将形成环的边记录下来，之后再用这个形成环的边上的一点把不连通的部分连到一起。（最后每连一条边都要调用一次mix函数）

#include <bits/stdc++.h>
using namespace std;
int n,pre[1015];
struct node{
int x,y;
};
node point[1015];
int Find(int x){
return x==pre[x]?x:Find(pre[x]);
}
void mix(int x,int y){
int xx=Find(x);
int yy=Find(y);
if(xx!=yy){
pre[xx]=yy;
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
int k=0,a,b;
for(int i=0;i<1005;i++)
pre[i]=i;
for(int i=0;i<n-1;i++){
scanf("%d%d",&a,&b);
if(Find(a)!=Find(b))
mix(a,b);
else{
point[k].x=a;
point[k].y=b;
k++;
}
}
printf("%dn",k);
for(int i=0;i<k;i++){
printf("%d %d ",point[i].x,point[i].y);
for(int j=1;j<=n;j++){
a=Find(j);
b=Find(point[i].x);
if(a!=b){
mix(j,point[i].x);
printf("%d %dn",point[i].x,j);
break;
}
}
}
}
return 0;
}