题意:乱序给你树上的每一个节点与之相距<=2的节点集合(并不知道这具体是哪个节点)。

还原整棵树。

标程:

 #include<bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
const int N=;
vector<P> vec[N];
bitset<N> bit[N];
int n,f[*N],x,u,v,k;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void merge(int x,int y){f[find(x)]=find(y);}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d",&k);
while (k--) scanf("%d",&x),bit[x][i]=;
}
if (n==) return puts("1 2"),;
for (int i=;i<=*n;i++) f[i]=i;
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++)
{
int cnt=(int)(bit[i]&bit[j]).count();
if (cnt==) merge(i,j),merge(i+n,j+n);
else if (cnt==) merge(i+n,j),merge(i,j+n);
else vec[cnt].push_back(P(i,j));
}
if (vec[n].size()==n*(n-)/)//特判星
{
for (int i=;i<=n;i++) printf("1 %d\n",i);
return ;
}
if (vec[n].size()==)//特判流星锤
{
printf("%d %d\n",u=vec[n][].fir,v=vec[n][].sec);
for (int i=;i<=n;i++)
if (i!=u&&i!=v) {merge(i,u),merge(i+n,u+n),merge(i+n,v),merge(i,v+n);break;}
for (int i=;i<=n;i++)
if (i!=u&&i!=v)
if (find(i)==find(u)) printf("%d %d\n",i,u);else printf("%d %d\n",i,v);
return ;
}
for (int i=n;i>=;i--)
for (int j=;j<vec[i].size();j++)
if (u=vec[i][j].fir,v=vec[i][j].sec,find(u)!=find(v))
{
printf("%d %d\n",u,v);
merge(u+n,v);merge(u,v+n);
}
return ;
}

注意有很多特判:n=2,星星图,流星锤图(后两个由于不满足贪心)。

题解:贪心+染色

考虑对相邻节点集合取交,设大小为cnt。若cnt=1,这两个点必同色;cnt=2,必异色。剩下的存入一个vector。然后按cnt从大到小枚举两点,如果他们不在同色区间中,相信它们之间有边。并更新并查集。

最新文章

  1. 使用maven镜像
  2. css的两种盒子模型
  3. 整理一些有意思的php笔试题
  4. VS2010生成Qt程序图标修改方法
  5. P147、面试题26:复杂链表的复制
  6. ios 获取字符串所需要占用的label的高度
  7. Xcode 升级后, 插件无法使用的问题( PluginLoading: Required plug-in compatibility UUID.... )
  8. 03_MySQL中文乱码处理_02_确保MySQL插入数据不乱码的解决方法
  9. RStudio版本号管理 整合Git
  10. 批量自动更新SVN版本库 - Windows
  11. Vue 事件
  12. python小白之路
  13. Libgdx 1.5.2发布
  14. 【spring源码分析】IOC容器初始化(五)
  15. git私有仓库与pycharm联合使用
  16. flask 虚拟换将安装
  17. fabric私密数据学习笔记
  18. Python爬虫之使用Fiddler+Postman+Python的requests模块爬取各国国旗
  19. C++类相关
  20. k64 datasheet学习笔记3---Chip Configuration之Clock modules

热门文章

  1. rabbitmq一个连接多个信道channel
  2. jquey弹出框demo
  3. 0001.第一个多线程demo--分批处理数据
  4. C++ 浅析移位运算
  5. Hashtable、HashMap、TreeMap、ConcurrentHashMap、ConcurrentSkipListMap区别
  6. linux部署jdk-tomcat
  7. Python--JavaScript的对象
  8. 【Flutter学习】之绘画实例(一)
  9. Python基础(二):斐波那契数列、模拟cp操作、生成8位随机密码
  10. BZOJ 2653: middle(主席树+二分答案)