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

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 –

Codeforcs Round 529 Div. 3 D Solution

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

using namespace std;

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

ll a[N],b[N],vis[N];

void dfs(ll s)
    for(ll i=0;i<v[s].size();i++)

int main()
    ll 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
            v[i].pb(b[i]);//Connecting kid i with ai2
            v[b[i]].pb(a[i]);//Connecting kid ai2 with ai1
    for(auto it : c)cout<<it<<" ";
    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

Codeforces sahal

Leave your comment