题解 CF25D 【Roads not only in Berland】

2018-06-29 15:15:55


首先拆边的时候,肯定拆没用的边,换句话说就是,两个点已经联通了,再在这两个点上添加边,肯定就是没用的咯。

刚开始,所有点都是一个独立的集合,每当要添加一条新边的时候,判断该边连接的两点是否在同一个集合中,如果已经是同一个集合,那么该边就是没用的边。如果不在一个集合,那么就把该边连接的两点的所属集合合并——并查集

之后扫描任意两点,如果某两点不在同一个集合中,那么就添加一条边,使这两点联通,把该两点所属的集合合并。

主要就这么多,具体详细只能看代码了

LuckyCloud
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct edge
{
  int u,v;
}del[4000];
struct data
{
 int u,v,x,y;
}Item[4000];
int fa[1013],sum[1013],tot,n,x,y,fx,fy,ans;
inline int find(int x)
{
  if (fa[x]==x) return x;
  fa[x]=find(fa[x]);
  return fa[x];
}
inline long long read()
{
  long long cnt=0,f=1;char ch=getchar();
  while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
  while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
  return cnt*f;
}
void load()
{
  for (int i=1;i<=n;i++)
   fa[i]=i;
}
int main()
{
  n=read();
  load();
  for (int i=1;i<n;i++)
   {
    x=read();y=read();
    fx=find(x);fy=find(y);
    if (fx!=fy) fa[fy]=fx;
    else {del[++tot].u=x;del[tot].v=y;}
   }
  for (int i=1;i<n;i++)
   for (int j=i+1;j<=n;j++)
    {
      fx=find(i);fy=find(j);
      if (fx!=fy)
       {
        fa[fy]=fx;
        Item[++ans].u=del[tot].u;
        Item[ans].v=del[tot--].v;
        Item[ans].x=i;
        Item[ans].y=j;
       }
    }   
  printf("%d\n",ans);
  for (int i=1;i<=ans;i++)
   printf("%d %d %d %d\n",Item[i].u,Item[i].v,Item[i].x,Item[i].y);
  return 0;
}