Random Graph

struct Link{int frm,to,nxt; long long w;};

邻接表存边。

struct rdGraph
{
    int n,m,tot,Head[Maxlen],fa[Maxlen];
    long long rdMin,rdMax;
    bool isDir,isCon,isRep,isVal;
    Link Edge[Maxlen*2];
    int Find(int x);
    void Addedge(int x,int y,ll z);
    bool isConnect(int x,int y);
};

第一行：点数，边数，邻接表开头，并查集父亲。

第二行：边权最小值和最大值。

第三行：是否有方向，是否连通，是否有重边和自环，是否有边权。

第四行：邻接表。

第五行：并查集找祖先的函数。

第六行：加边函数。

第七行：查询是否连通的函数。

struct rdTree:rdGraph
{
    int typ;
};

rdTree 继承自 rdGraph，多了一个表示类别的 typ 变量。

接下来是关于随机图的构造函数：

rdGraph RandGraph(int n,int m,bool isDir=false,bool isCon=false,bool isRep=false,long long rdMin=1,long long rdMax=1)

构造一个 点 边的随机图。

rdGraph RandHackSPFA(int n,int m,bool isDir=false,long long rdMin=1,long long rdMax=1)

构造一个卡 SPFA 的随机图。

rdGraph RandDAG(int n,int m,long long rdMin=1,long long rdMax=1)

构造一个随机的 DAG。

rdTree RandTree(int n,long long rdMin=1,long long rdMax=1)

利用 Prufer 序列构造一棵随机树，相当于 RandGraph(n,n-1,false,true)。

rdTree RandBranch(int n,int branch=int(1e9),long long rdMin=1,long long rdMax=1)

构造一棵叉数为 branch 的随机树，数据较弱。

rdTree RandChain(int n,bool isSorted=true,long long rdMin=1,long long rdMax=1)

构造一条随机的链，相当于 RandBranch(n,1)。

rdTree RandFlower(int n,int root=1,long long rdMin=1,long long rdMax=1)

构造一个随机的菊花图，相当于 RandBranch(n,n-1)。

rdTree RandBinaryTree(int n,long long rdMin=1,long long rdMax=1)

利用括号序列构造一棵随机的二叉树，较 RandBranch(n,2) 数据稍强。