建树
老姚式建树（期望深度：log（n））
#include<bits/stdc++.h>
using namespace std;
int main(){
srand(time(0));srand(rand());
int n=100;
printf("%d
",n);
for(int i=2;i<=n;i++){
printf("%d %d
",i,rand()%(i-1)+1);
}
}
skyh式建树（期望深度：sqrt（n））
#include<bits/stdc++.h>
using namespace std;
const int maxn=150;
int fa[maxn];
int find_root(int x){return fa[x]==x?x:fa[x]=find_root(fa[x]);}
int main(){
srand(time(0));srand(rand());
int n=100,cnt=n;
printf("%d
",n);
for(int i=1;i<=n;i++)fa[i]=i;
int tot=0;
while(cnt!=1){
int x=rand()%n+1,y=rand()%n+1;
if(find_root(x)==find_root(y))continue;
fa[find_root(x)]=find_root(y);
printf("%d %d
",x,y);cnt--;
}
}
建图
联通图，建树连边
#include<bits/stdc++.h>
using namespace std;
const int maxn=150;
int fa[maxn];
int find_root(int x){return fa[x]==x?x:fa[x]=find_root(fa[x]);}
int main(){
srand(time(0));srand(rand());
int n=100,m=300,cnt=n;
printf("%d %d
",n,m);
for(int i=1;i<=n;i++)fa[i]=i;
while(cnt!=1){
int x=rand()%n+1,y=rand()%n+1;
if(find_root(x)==find_root(y))continue;
fa[find_root(x)]=find_root(y);
printf("%d %d
",x,y);cnt--;
}
for(int i=1;i<=m-n+1;i++){
int x=rand()%n+1,y=rand()%n+1;
while(x==y)x=rand()%n+1,y=rand()%n+1;
printf("%d %d
",x,y);
}
}
DAG图
#include<bits/stdc++.h>
#define build HASH(int _nxt,int _x,int _y){nxt=_nxt,x=_x,y=_y;}
using namespace std;
const int maxn=1e5+10,mod=59999;
int n=100,m=150;//调整
int ver[maxn<<1],nxt[maxn<<1],head[maxn],tot,cntt=n;
int dfn[maxn],low[maxn],fa[maxn],sta[maxn],belong[maxn],top,cnt,num,CNT;
bool ins[maxn];
vector<int>scc[maxn];
void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
int find_root(int x){return fa[x]==x?x:fa[x]=find_root(fa[x]);}
void Build_Map(){
while(cntt!=1){
int x=rand()%n+1,y=rand()%n+1;
if(find_root(x)==find_root(y))continue;
fa[find_root(x)]=find_root(y);
cntt--;
if((rand()%2)&1)add(x,y);
else add(y,x);
}
for(int i=1;i<=m-n+1;i++){
int x=rand()%n+1,y=rand()%n+1;
while(x==y)x=rand()%n+1,y=rand()%n+1;
if((rand()%2)&1)add(x,y);
else add(y,x);
}
}
void tarjan(int x){
dfn[x]=low[x]=++num;
sta[++top]=x,ins[x]=1;
for(int i=head[x];i;i=nxt[i])
if(!dfn[ver[i]]){
tarjan(ver[i]);
low[x]=min(low[x],low[ver[i]]);
}
else if(ins[ver[i]])low[x]=min(low[x],dfn[ver[i]]);
if(dfn[x]==low[x]){
cnt++;int y;
do{
y=sta[top--],ins[y]=0;
belong[y]=cnt,scc[cnt].push_back(y);
}while(x!=y);
}
}
struct EDGE{
int x,y;
EDGE(){}
EDGE(int _x,int _y){x=_x,y=_y;}
}edge[maxn<<1];
int head_ha[maxn],hac;
struct HASH{int nxt,x,y;HASH(){};build;}Hash[maxn<<1];
void hash_add(int x,int y){
int ha=(x*maxn+y)%mod;
Hash[++hac]=HASH(head_ha[ha],x,y);
head_ha[ha]=hac;
}
bool find(int x,int y){
int ha=(x*maxn+y)%mod;
for(int i=head_ha[ha];i;i=Hash[i].nxt)
if(Hash[i].x==x&&Hash[i].y==y)
return 1;
return 0;
}
int main(){
srand(time(0));srand(rand());
for(int i=1;i<=n;i++)fa[i]=i;
Build_Map();
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(belong[x]==belong[y])continue;
if(find(belong[x],belong[y])==0)hash_add(belong[x],belong[y]),edge[++CNT]=EDGE(belong[x],belong[y]);
}
}
printf("%d %d
",cnt,CNT);
for(int i=1;i<=CNT;i++)printf("%d %d
",edge[i].x,edge[i].y);
}
洛谷
import random
list_like = lambda data: isinstance(data, tuple) or isinstance(data, list)
class Edge:
def __init__(self, u, v, w):
self.start, self.end, self.weight = u, v, w
def __str__(self):
return "{} {} {}".format(self.start, self.end, self.weight)
@staticmethod
def unweighted_edge(edge):
return '{} {}'.format(edge.start,edge.end)
class Graph:
def __init__(self, point_count, directed=False):
self.directed, self.edges = directed, [[] for i in range(point_count + 1)]
def to_str(self, **kwargs):
shuffle = kwargs.get("shuffle", False)
weighted = kwargs.get("weighted", False)
output = str if weighted else Edge.unweighted_edge
buf = []
if shuffle:
new_node_id = [i for i in range(1, len(self.edges))]
random.shuffle(new_node_id)
new_node_id = [0] + new_node_id
edge_buf = []
for edge in self.iterate_edges():
edge_buf.append(Edge(new_node_id[edge.start], new_node_id[edge.end], edge.weight))
random.shuffle(edge_buf)
for edge in edge_buf:
if not self.directed and random.randint(0, 1) == 0:
(edge.start, edge.end) = (edge.end, edge.start)
buf.append(output(edge))
else:
for edge in self.iterate_edges():
buf.append(output(edge))
return "
".join(buf)
def print(self, **kwargs):
print(self.to_str(**kwargs))
def iterate_edges(self):
for node in self.edges:
for edge in node:
if edge.end >= edge.start or self.directed:
yield edge
def __add_edge(self, x, y, w):
self.edges[x].append(Edge(x, y, w))
def add_edge(self, x, y, **kwargs):
weight = kwargs.get("weight", 1)
self.__add_edge(x, y, weight)
if not self.directed and x != y:
self.__add_edge(y, x, weight)
@staticmethod
def chain(point_count, **kwargs):
return Graph.tree(point_count, 1, 0, **kwargs)
@staticmethod
def flower(point_count, **kwargs):
return Graph.tree(point_count, 0, 1, **kwargs)
@staticmethod
def tree(point_count, chain=0, flower=0, **kwargs):
directed = kwargs.get("directed", False)
weight_limit = kwargs.get("weight_limit", (1, 1))
if not list_like(weight_limit):
weight_limit = (1, weight_limit)
weight_gen = kwargs.get("weight_gen", lambda: random.randint(weight_limit[0], weight_limit[1]))
if not 0 <= chain <= 1 or not 0 <= flower <= 1:
raise Exception("chain and flower must be between 0 and 1")
if chain + flower > 1:
raise Exception("chain plus flower must be smaller than 1")
graph = Graph(point_count, directed)
chain_count = int((point_count - 1) * chain)
flower_count = int((point_count - 1) * flower)
if chain_count > point_count - 1:
chain_count = point_count - 1
if chain_count + flower_count > point_count - 1:
flower_count = point_count - 1 - chain_count
random_count = point_count - 1 - chain_count - flower_count
for i in range(2, chain_count + 2):
graph.add_edge(i - 1, i, weight=weight_gen())
for i in range(chain_count + 2, chain_count + flower_count + 2):
graph.add_edge(1, i, weight=weight_gen())
for i in range(point_count - random_count + 1, point_count + 1):
u = random.randrange(1, i)
graph.add_edge(u, i, weight=weight_gen())
return graph
@staticmethod
def binary_tree(point_count, left=0, right=0, **kwargs):
directed = kwargs.get("directed", False)
weight_limit = kwargs.get("weight_limit", (1, 1))
if not list_like(weight_limit):
weight_limit = (1, weight_limit)
weight_gen = kwargs.get(
"weight_gen", lambda: random.randint(
weight_limit[0], weight_limit[1]))
if not 0 <= left <= 1 or not 0 <= right <= 1:
raise Exception("left and right must be between 0 and 1")
if left + right > 1:
raise Exception("left plus right must be smaller than 1")
can_left = set([1])
can_right = set([1])
graph = Graph(point_count, directed)
for i in range(2, point_count + 1):
edge_pos = random.random()
node = 0
# Left
if edge_pos < left or left + right < edge_pos <= (1.0 - left - right) / 2:
node = random.choice(tuple(can_left))
can_left.remove(node)
# Right
elif left <= edge_pos <= left + right or (1.0 - left - right) / 2 < edge_pos < 1:
node = random.choice(tuple(can_right))
can_right.remove(node)
graph.add_edge(node, i, weight=weight_gen())
can_left.add(i)
can_right.add(i)
return graph
@staticmethod
def graph(point_count, edge_count, **kwargs):
directed = kwargs.get("directed", False)
self_loop = kwargs.get("self_loop", False)
repeated_edges = kwargs.get("repeated_edges", False)
weight_limit = kwargs.get("weight_limit", (1, 1))
if not list_like(weight_limit):
weight_limit = (1, weight_limit)
weight_gen = kwargs.get(
"weight_gen", lambda: random.randint(
weight_limit[0], weight_limit[1]))
graph = Graph(point_count, directed)
used_edges = set()
i = 0
while i < edge_count:
u = random.randint(1, point_count)
v = random.randint(1, point_count)
if (not self_loop and u == v) or (not repeated_edges and (u, v) in used_edges):
# Then we generate a new pair of nodes
continue
graph.add_edge(u, v, weight=weight_gen())
if not repeated_edges:
used_edges.add((u, v))
if not directed:
used_edges.add((v, u))
i += 1
return graph
@staticmethod
def DAG(point_count, edge_count, **kwargs):
if edge_count < point_count - 1:
raise Exception("the number of edges of connected graph must more than the number of nodes - 1")
self_loop = kwargs.get("self_loop", False) # DAG default has no loop
repeated_edges = kwargs.get("repeated_edges", True)
loop = kwargs.get("loop", False)
weight_limit = kwargs.get("weight_limit", (1, 1))
if not list_like(weight_limit):
weight_limit = (1, weight_limit)
weight_gen = kwargs.get(
"weight_gen", lambda: random.randint(
weight_limit[0], weight_limit[1]))
used_edges = set()
edge_buf = list(Graph.tree(point_count, weight_gen=weight_gen).iterate_edges())
graph = Graph(point_count, directed=True)
for edge in edge_buf:
if loop and random.randint(1, 2) == 1:
edge.start, edge.end = edge.end, edge.start
graph.add_edge(edge.start, edge.end, weight=edge.weight)
if not repeated_edges:
used_edges.add((edge.start, edge.end))
i = point_count - 1
while i < edge_count:
u = random.randint(1, point_count)
v = random.randint(1, point_count)
if not loop and u > v:
u, v = v, u
if (not self_loop and u == v) or (not repeated_edges and (u, v) in used_edges):
# Then we generate a new pair of nodes
continue
graph.add_edge(u, v, weight=weight_gen())
if not repeated_edges:
used_edges.add((u, v))
i += 1
return graph
@staticmethod
def UDAG(point_count, edge_count, **kwargs):
if edge_count < point_count - 1:
raise Exception("the number of edges of connected graph must more than the number of nodes - 1")
self_loop = kwargs.get("self_loop", True)
repeated_edges = kwargs.get("repeated_edges", True)
weight_limit = kwargs.get("weight_limit", (1, 1))
if not list_like(weight_limit):
weight_limit = (1, weight_limit)
weight_gen = kwargs.get(
"weight_gen", lambda: random.randint(
weight_limit[0], weight_limit[1]))
used_edges = set()
graph = Graph.tree(point_count, weight_gen=weight_gen, directed=False)
for edge in graph.iterate_edges():
if not repeated_edges:
used_edges.add((edge.start, edge.end))
used_edges.add((edge.end, edge.start))
i = point_count - 1
while i < edge_count:
u = random.randint(1, point_count)
v = random.randint(1, point_count)
if (not self_loop and u == v) or (not repeated_edges and (u, v) in used_edges):
# Then we generate a new pair of nodes
continue
graph.add_edge(u, v, weight=weight_gen())
if not repeated_edges:
used_edges.add((u, v))
used_edges.add((v, u))
i += 1
return graph
@staticmethod
def hack_spfa(point_count, **kwargs):
directed = kwargs.get("directed", False)
extraedg = kwargs.get("extra_edge", 2)
weight_limit = kwargs.get("weight_limit", (1, 1))
if not list_like(weight_limit):
weight_limit = (1, weight_limit)
weight_gen = kwargs.get(
"weight_gen", lambda: random.randint(
weight_limit[0], weight_limit[1]))
point_to_skip = point_count + 3
graph = Graph(point_count, directed)
if point_count % 2 == 1:
point_to_skip = point_count / 2 + 1
half = int(point_count / 2)
for i in range(1, half):
(x, y) = (i, i + 1)
graph.add_edge(x + (x >= point_to_skip), y +
(y >= point_to_skip), weight=weight_gen())
(x, y) = (i + half, i + half + 1)
graph.add_edge(x + (x >= point_to_skip), y +
(y >= point_to_skip), weight=weight_gen())
for i in range(1, half + 1):
(x, y) = (i, i + half)
graph.add_edge(x + (x >= point_to_skip), y +
(y >= point_to_skip), weight=weight_gen())
for i in range(extraedg):
u = random.randint(1, point_count)
v = random.randint(1, point_count)
graph.add_edge(u, v, weight=weight_gen())
return graph
n = 10
m = 20
print(n, m)
Graph.graph(n, m, weight_limit=5).print(weighted=True)