CFR 330 E. Graph Reconstruction ( Random Search )

Problem - E - Codeforces
The deterministic solution for this problem is quite difficult. However, it is easy to come up with a randomised algorithm. There are primarily 2 types of randomised algorithms, Monte Carlo that runs in a certain time but do not always guarantee an optimal answer, Las Vegas that guarantees correct answer but might run forever ( or until all possible states are examined ). For this problem, since the degrees for each vertex are to be between 1 and 2, and the number of edges do not exceed the number of vertices, we can actually describe the answer as an array, where each vertex has an edge with its adjacent vertices in the array. Being able to generate possible cases, we will try to run a Las Vegas algorithm, which continues trying randomly generated cases until some valid sequence is found. However, since there is time bound, and no solution might be possible, we will maximise the number of cases to try, that will not exceed the time limit, and if no valid sequence is found, determine that there is no solution at all. So in the end it turns out be a Monte Carlo algorithm.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
typedef pair< int, int > pii;

int n, m;
set< pii > has_edge;

int v[ MAXN ];

bool randSolve(){
    random_shuffle( v, v + n );
    for( int i = 0; i < m; ++i )
        if( has_edge.count( pii( v[ i ], v[ ( i + 1 ) % n ] ) ) )
            return false;
    for( int i = 0; i < m; ++i )
        printf("%d %d\n", v[ i ], v[ ( i + 1 ) % n ]);
    return true;
}

void solve(){
    for( int i = 0; i < n; ++i )
        v[ i ] = i + 1;
    for( int i = 0; i < 1000; ++i ){
        if( randSolve() )
            return;
    }
    puts("-1");
}

int main(){
    scanf("%d%d", &n, &m);
    for( int i = 0; i < m; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        has_edge.insert( pii( u, v ) );
        has_edge.insert( pii( v, u ) );
    }
    solve();
    return 0;
}