graph_make.cpp

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

uniform_int_distribution<int> a_dis(1, 1000'000'000);
int find_empty(vector<vector<int>> &adj,int i=0){
    if(adj[i].size()==0 || adj[i].size()==1){ return i;} 
    else {
        return find_empty(adj,adj[i][a_dis(rng)%adj[i].size()]);
    }
}

vector<vector<int>> n_dir_tree(int n,double p){
    vector<vector<int>> adj(n);


    bernoulli_distribution dist(p);

    stack<int> stk;stk.push(0);

    int i=1;
    while(i<n){
        int parent;
        if(stk.empty()){
            parent = find_empty(adj);
        }
        else{parent = stk.top();stk.pop();}
        while(dist(rng)&&i<n){
            adj[parent].push_back(i);
            stk.push(i);
            i++;
        }
    }
    return adj;
}

void make_undir(vector<vector<int>> &adj){
    int n=adj.size();
    vector<pair<int,int>> extra;extra.reserve(n);
    for(int i = 0; i < n; i++){
        for(int v : adj[i]){
            if(find(adj[v].begin(), adj[v].end(), i) == adj[v].end()){
                extra.push_back({v,i});
            }
        }
    }

    for(auto &e : extra){
        adj[e.first].push_back(e.second);
    }
}

void shuffle_graph(vector<vector<int>> &adj){ //Our creation puts them in topological sorted order[0,n-1], so we can shuffle,
    int n = adj.size();

    vector<int> remap(n);
    for(int i=0;i<n;i++){
        remap[i] = i;
    }shuffle(remap.begin(),remap.end(),rng);

    vector<vector<int>> new_adj(n);
    for(int i = 0; i < n; i++){
        int par = remap[i];
        for(int cld : adj[i]){
            new_adj[par].push_back(remap[cld]);
        }
    }

    adj = move(new_adj);
}

void add_edges(vector<vector<int>> &adj,int k,bool keepdir=true){ //Keep the topo order
    int n = adj.size();
    uniform_int_distribution<int> dist(0, n-1);

    while(k--){
        int u = dist(rng);
        int v = dist(rng);

        if(u>=v && keepdir){
            k++;
            continue;
        }
        if(find(adj[u].begin(), adj[u].end(), v) != adj[u].end()){
            k++;
            continue;
        }      

        adj[u].push_back(v);
    }
}

int main(){
    int n;cin>>n;

    double p=0.4;

    vector<vector<int>> adj = n_dir_tree(n,p);
    add_edges_keep_dag(adj,n/4);
    //make_undir(adj);
    shuffle_graph(adj);
    for(int i=0;i<n;i++){
        cout<<'"'<<i<<"\" : [";
        for(int j=0;j<adj[i].size();j++){
            cout<<'"'<<adj[i][j]<<"\"";
            if(j!=adj[i].size()-1){cout<<',';}
        }cout<<"],\n";
    }cout<<endl;

}