In this HackerEarth Graphs problem solution, You are given an undirected graph G that contains n nodes and m edges. It is also mentioned that G does not contain any cycles. A sequence of nodes (A1,A2,A3,...Ak) is special if distance  d(Ai.Ai+1) = f.i for all 1<=i<k , and all Ai are distinct. Determine the size of a maximal special sequence. Hence, the one with maximum k.

HackerEarth Graphs problem solution


HackerEarth Graphs problem solution.

#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define leadzero(a) __builtin_clz(a) // count leading zeroes
#define trailzero(a) __builtin_ctz(a) // count trailing zeroes
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln endl
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<" Term "<< ++c <<" = "<<it<<ln;} cerr<<endl
#define dbgstlp32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<" Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cerr<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inp freopen("input.txt", "r", stdin)
#define outp freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
out<<"{ ";
forstl(x,c) out<<x<<" ";
out<<"}"; return out;
}
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const ll MOD = 1e9+7, LIM = 1e5+5;
const ld EPS = 1e-9;

int main(){
fastio;

int n,m,f;
cin>>n>>m>>f;
v32 adj[n];
forn(i,m){
int x,y;
cin>>x>>y;
x--;
y--;
adj[x].pb(y);
adj[y].pb(x);
}

int visited[n] = {0};
int par[n] = {0};
int dist[n] = {0};

int maxval = 0, posn = -1;

forn(i,n){
if(visited[i]>0) continue;

queue<int> q;
visited[i] = 1;
q.push(i);
int t = 0;
while(!q.empty()){
t = q.front();
q.pop();

forstl(r, adj[t]){
if(visited[r]>0) continue;
visited[r] = 1;
q.push(r);
}
}
int end = t;

q.push(end);
visited[end] = 2;
dist[end] = 1;
par[end] = -1;
while(!q.empty()){
t = q.front();
q.pop();

forstl(r, adj[t]){
if(visited[r]>1) continue;
visited[r] = 2;
q.push(r);
dist[r] = dist[t]+1;
par[r] = t;
}
}
if(dist[t]>maxval){
maxval = dist[t];
posn = t;
}
}

v32 v;
int num = 0;
while(posn != -1){
if(num == 0) v.pb(posn);
num++;
if(num == f) num = 0;
posn = par[posn];
}

v32 answer;
int g = v.size()/2;
int ptr1 = g, ptr2 = g-1;

while(ptr1 <v.size() || ptr2 >=0){
answer.pb(v[ptr1]);
if(ptr2 < 0) break;
answer.pb(v[ptr2]);
ptr1++;
ptr2--;
}

cout<<answer.size()<<ln;

return 0;
}