codeforces 25D

n 个点 n-1条边  不一定是树

要把它变成一棵树  最少要删除几条边

每删除一条边可以在另外地方造一条边

并查集

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>

using namespace std;

#define LL long long
#define MAXN 1010
#define inf  1000000000

int f[MAXN];
int find1(int a)
{
    if(a==f[a])
        return a;
    else
    {
        int b=find1(f[a]);
        return f[a]=b;
    }
}
int ii[MAXN],jj[MAXN],u[MAXN],v[MAXN];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            f[i]=i;
        int cnt=0;

        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int fa,fb;
            fa=find1(a);
            fb=find1(b);
            if(fa!=fb)
                f[fa]=fb;
            else
            {
                ii[cnt]=a;
                jj[cnt]=b;
                cnt++;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int fa=find1(i);
            for(int j=i+1;j<=n;j++)
            {
                int fb=find1(j);
                if(fa!=fb)
                {
                    f[fb]=fa;
                    u[ans]=i;
                    v[ans++]=j;
                }
            }
        }
        printf("%d
",ans);
        for(int i=0;i<ans;i++)
            printf("%d% d %d %d
",ii[i],jj[i],u[i],v[i]);
    }
    return 0;
}