数据生成 -- 树_ramay7的博客-程序员秘密

生成一个 $n$ 个节点的树和 $n-1$ 条无向边（无边权），生成数据时需要注意无重边，无环，和所有节点编号都要在边的信息中出现。我是把最后一条边设为 $(n-1,n)$ ，并且在之前保证这两个节点不连通。这个似乎破坏了一些随机性:)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <time.h>
#include <set>
using namespace std;
typedef long long ll;
const int MAX_N = 1000;
const int MAX_M = 1000010;

int father[MAX_M];

int find(int x)
{
    return father[x] == x ? x : father[x] = find(father[x]);
}

int main()
{
    //freopen("GenerateTree.in", "w", stdout);
    srand((unsigned)time(NULL));
    int n, tmp, u, v;
    for (int i = 1; i < MAX_N; ++i) {
        n  = i * 10;
        printf("%d\n", n);
        set<pair<int, int > > s;
        for (int j = 1; j <= n; ++j) { father[j] = j; }
        for (int j = 1; j < n - 1; ++j) { // 保证每个节点编号都出现
            while(1) {
                    tmp = rand() % n + 1;
                    if (tmp == j) continue;
                    if (s.find(make_pair(tmp, j)) != s.end()) continue;  // 防止出现重边
                    if (s.find(make_pair(j, tmp)) != s.end()) continue;
                    u = find(j);
                    v = find(tmp);
                    if (tmp == n -1 && find(n - 1) == find(n)) continue; // 防止和最后一条边n-1~n出现环
                    if (tmp == n && find(n) == find(n - 1)) continue;
                    if (u != v) break; // 防止出现环
            }
            printf("%d %d\n", j, tmp);
            s.insert(make_pair(j, tmp));
            s.insert(make_pair(tmp, j));
            father[u] = v;
        }
        printf("%d %d\n", n - 1, n);
    }
    return 0;
}

本文链接：https://blog.csdn.net/Ramay7/article/details/52102166

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

nginx安装和配置和EMQX的安装和启动_emqx nginx_倚天仗剑走天涯WGM的博客-程序员秘密

1.安装参见Windows下Nginx安装与配置教程https://cloud.tencent.com/developer/article/1333800配置参见：解密TLS协议全记录之Openssl的使用与Nginx Server的配置https://blog.csdn.net/walleva96/article/details/107093500

linux带多个参数返回json,在JS方法中返回多个值的三种方法_天青色水玉的博客-程序员秘密

在使用JS编程中，有时需要在一个方法返回两个个或两个以上的数据，用下面的几种方法都可以实现：1 使用数组的方式，如下：JS函数返回多个值--oec2003function getData(){var names=new Array("oec2003","oec2004");return names;}function getNames(){var names=getData();alert(get...

SAP将内表生成XML作为excel保存到FTP_weixin_34416649的博客-程序员秘密

最近遇到了一个需求，在sap后台按月将数据导入到ftp服务器上，并保存为excel文件。之前的做法是将文件生成到本地，然后上传到sap服务器上。但是sap服务器后台运行程序的时候并不存在本地路径，因此要求直接将内表保存为excel格式传输到ftp上。据我了解，sap并不支持ole的传输，于是就想到使用xml方式传输到ftp上，然后将扩展名保存为*.xls同样可以使用excel打开。于是...

释放表空间更新Oracle数据库,exp导出 imp导入数据库_oracle 导出再导入能释放表空间吗_LMGD的博客-程序员秘密

释放表空间更新数据库：注：需要重新创建用户直接从第3步开始，需要释放以前的表空间和删除用户从步骤1开始释放表空间drop tablespace orderweb(表空间名字)including contents and datafiles;注：表空间以及数据文件会一起删除级联,就把这个用户下的所有东西都给删掉级联删除用户drop user orderweb_zzzzyy cascade; 遇到的问题：如果执行上面的删除命令出现“oracle无法删除当前连接...

KNN算法思想及算法描述和优缺点_knn算法原理及优缺点_cdy艳0917的博客-程序员秘密

KNN适用于分类的，不需要训练，该算法所选的邻居都是已经正确分类的对象。该算法在定类决策上只依据最邻近的一个或者几个样本类别来决定待分类样本所属的类别KNN算法的思路：KNN是通过不同特征之间的距离进行分类的。如果一个样本在特征空间中的K个最相似的样本中的大多数属于同一类别，则该样本也属于这一类别，其中K通常是不大于20的整数。KNN算法得结果很大程度上取决于K的选择KNN算法的思想：在训练集的数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练与之最

定时任务莫名停止，Spring 定时任务存在 Bug？？_springboot spring.task.scheduling.pool.size 不生效_楼下小黑哥的博客-程序员秘密

Hello~各位读者新年好！这里楼下小黑哥给大家拜个年，祝大家蒸蒸日上烫烫烫，年年有余屯屯屯。那年那 Bug春节放假，小黑哥坐上高铁回家，突然想到一次生产问题。那是小黑哥参加工作第一年，那一年国庆假期，小黑哥提前一天请假回家办个护照。那时候刚开始负责一个生产系统，所以工作日请假，还是有点担心，就怕问题看小黑哥不在，悄然上门。哎，真实越怕什么，就来什么。高铁开到一半的时候，同事反馈系统不能...