Codeforces Round 529(Div. 3) D. Circular Dance – Solution

Today we will talk about the solution of a codeforces problem. Here in this problem n kids are dancing. The kids are numbered from 1 to n. Each kid remembers that which 2 kids were in front of him/her but order of those 2 is not remembered. So, to solve this problem we will create a circular directed graph and run dfs algorithm. Let’s see the solution through an example –

Here, kid 3 and kid 5 are in front of kid 1. So, in the input it can be given as 3 5 or 5 3.

Now, for every kid we will check that which order is correct. For example, for kid 1

• If it is 3 5 then kid 3 has kid 5 in front of him so we will connect kid 1 with kid 3 and kid 3 with kid 5 in a 2D vector.

• If it is 5 3 then kid 5 has kid 3 in front of him so we will connect kid 1 with kid 5 and kid 5 with kid 3 in a 2D vector.

In this way we will create a circular graph. Then we have to just iterate over the graph vertices and print them. Here i have used dfs algorithm for graph traversal.

Source Code

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


#define pb(a)               push_back(a)
#define ll                  long long
#define for1(i,n)           for(int i=1;i<=n;i++)


vector<ll>v[N];
ll a[N],b[N],vis[N];
vector<ll>c;

void dfs(ll s)
{
    c.pb(s);
    vis[s]=1;
    for(ll i=0;i<v[s].size();i++)
    {
        if(vis[v[s][i]]==0)
        {
            dfs(v[s][i]);
        }
    }
}

int main()
{
    ll n;
    cin>>n;
    for1(i,n)
    {
        cin>>a[i]>>b[i];
    }
    for1(i,n)
    {
        if(a[a[i]]==b[i] || b[a[i]]==b[i])
        {
            v[i].pb(a[i]);//Connecting kid i with ai1
            v[a[i]].pb(b[i]);//Connecting kid ai1 with ai2
        }
        else
        {
            v[i].pb(b[i]);//Connecting kid i with ai2
            v[b[i]].pb(a[i]);//Connecting kid ai2 with ai1
        }
    }
    dfs(a[1]);
    for(auto it : c)cout<<it<<" ";
    cout<<endl;
    return 0;
}

You can also check these Smartphone Processor

I am a flying kite

I am a day dreamer

I am a moving pen

writing on a paper

• Twitter
• Facebook
• Instagram

Codeforces sahal