# 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

## Leave a Reply