Hello,

I need to build a connected graph with 1e5 vertices and 4e5 edges, but when I try to create using rand () I can not get such a graph. can anybody help me?

P.S. the edges must be different.

# | User | Rating |
---|---|---|

1 | tourist | 3539 |

2 | V--o_o--V | 3338 |

3 | Um_nik | 3307 |

4 | Petr | 3297 |

5 | ecnerwala | 3282 |

6 | LHiC | 3266 |

7 | wxhtxdy | 3264 |

8 | Radewoosh | 3257 |

9 | Vn_nV | 3182 |

10 | dotorya | 3178 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 207 |

2 | Errichto | 177 |

3 | neal | 159 |

4 | Ashishgup | 158 |

5 | PikMike | 157 |

6 | Petr | 156 |

6 | majk | 156 |

8 | rng_58 | 155 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

Hello,

I need to build a connected graph with 1e5 vertices and 4e5 edges, but when I try to create using rand () I can not get such a graph. can anybody help me?

P.S. the edges must be different.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/22/2019 23:11:04 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Maybe you can build a tree first: for i=2 to n link(i,rand()%(i-1)+1) (1-index) and then use another permutation of [1,n] to replace the original index.

After building the tree,add some arbitary edges. if you do not want to get repeated edges,use hash or map to check.

Getting all graphs with the same probability (that is, getting the uniform distribution) could be desirable. I guess you can use Prüfer codes if you just want a random tree on

nvertices. Even in this case, Wilson's algorithm for generating a spanning tree of a graphGuniformly at random is reasonably efficient.Example: What should be the probability of getting a 4-vertex star (that is, a tree with 3 leaves and a vertex of degree 3)? There are

n^{n - 2}labeled trees (Cayley), andnof those are stars because you can only choose the central vertex, so forn= 4 the correct probability is 4 / 4^{4 - 2}= 1 / 4.thanks

By the way, there exists extrimely convinient library jngen for these needs and similar.

SPOJ also has a useful test case generator.