Hey guys...
Recently I was solving this problem from CSES.
Here is what I have tried...
My idea
Firsly ,
- I am finding all cycles in graph
- For all nodes , keeping track of in which cycle it belongs to and what is the node no. in that cycle for that node.
- erasing all cycle causing edges
- then applying binary lifting on inverted tree.
now ready to answer queries.
if given starting node is involved any cycle then ending node should also be in same cycle. otherwise ans is -1.
If both are in same cycle then we can compute distance between them in O(1) using node nos. of both node.
Now , if Starting node is not in any cycle.
Then ending node must be ancestor of it otherwise ans is -1 (not reachable) Now as ending node is ancestor of starting node (talking in inverted tree) , we can walk upto that node and compute desired no. of jumps. It will be in O(logn).
By implementing this idea , I am getting WA in one TC ( Out of 11 ).
You can find my code here.
code
#include<bits/stdc++.h>
#define maxn 300005
#define ll long long int
using namespace std;
// https://cses.fi/problemset/task/1160/
set<int> par[maxn];
vector<int> nxt(maxn);
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);
vector<bool> v1(maxn,false),v2(maxn,false);
vector<vector<int>> cycle;
vector<int> tmp;
int cyc_id=0;
int nn=0;
int start=-1;
vector<int> tin(maxn),tout(maxn);
int tem=0;
vector<int> latkav;
void dfs(int n)
{
v1[n]=true;
int c=nxt[n];
if(v1[c] && !v2[c])
{
nxt[n]=-1;
par[c].erase(n);
latkav.push_back(n);
start=c;
}
if(!v1[c]) dfs(c);
if(start!=-1)
{
tmp.push_back(n);
kai_cyc[n]=cyc_id;
kyo_node[n]=nn++;
if(n==start)
{
cycle.push_back(tmp);
start=-1;
tmp.clear();
nn=0;
cyc_id++;
}
}
v2[n]=true;
}
vector<vector<int>> up;
int mxh;
void dfs1(int n,int p)
{
tin[n]=tem++;
up[n][0]=p;
for(int i=1;i<=mxh;i++)
{
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }
}
for(int c:par[n]) dfs1(c,n);
tout[n]=tem++;
}
bool isanc(int u,int v)
{
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
int main()
{
jaldi
int n,q;
cin>>n>>q;
for(int i=1,x;i<=n;i++)
{
cin>>x;
nxt[i]=x;
par[x].insert(i);
}
for(int i=1;i<=n;i++)
{
if(!v1[i]) dfs(i);
}
//for(vector<int> v:cycle) { deb(v); } //if in same cycle then o(1) ans, else binary lifting
mxh=ceil(log2(n));
up.assign(n+1,vector<int>(mxh+1,-1));
for(int x:latkav) dfs1(x,-1);
while(q--)
{
int start,end;
cin>>start>>end;
if(start==end) { cout<<"0\n"; continue; }
if(kai_cyc[start]!=-1)
{
if(kai_cyc[start]==kai_cyc[end])
{
int s=kyo_node[start];
int e=kyo_node[end];
int sz=cycle[kai_cyc[start]].size();
cout<<(s-e+sz)%sz<<"\n";
}
else { cout<<"-1\n"; }
continue;
}
if(isanc(end,start))
{
int jump=0;
for(int i=mxh;i>=0;i--)
{
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }
}
cout<<jump+1<<"\n";
}
else { cout<<"-1\n"; }
}
return 0;
}
So , can someone point out what am I doing wrong or any cases that I am missing.
Thanks in advance :)
UPD
As pwild sir pointed out , I was missing that cases.
To overcome that , I just added small logic to my code and it got ACCEPTED.
If you want to see code...
accepted code
#include<bits/stdc++.h>
#define maxn 200005
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// https://cses.fi/problemset/task/1160/
set<int> par[maxn];
vector<int> nxt(maxn);
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);
vector<bool> v1(maxn,false),v2(maxn,false);
vector<vector<int>> cycle;
vector<int> tmp;
int cyc_id=0;
int nn=0;
int start=-1;
vector<int> tin(maxn),tout(maxn);
int tem=0;
vector<int> latkav;
void dfs(int n)
{
v1[n]=true;
int c=nxt[n];
if(v1[c] && !v2[c])
{
par[c].erase(n);
latkav.push_back(n);
start=c;
}
if(!v1[c]) dfs(c);
if(start!=-1)
{
tmp.push_back(n);
kai_cyc[n]=cyc_id;
kyo_node[n]=nn++;
if(n==start)
{
cycle.push_back(tmp);
start=-1;
tmp.clear();
nn=0;
cyc_id++;
}
}
v2[n]=true;
}
vector<vector<int>> up;
int mxh;
void dfs1(int n,int p)
{
tin[n]=tem++;
up[n][0]=p;
for(int i=1;i<=mxh;i++)
{
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }
}
for(int c:par[n]) dfs1(c,n);
tout[n]=tem++;
}
bool isanc(int u,int v)
{
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
int main()
{
fastio
int n,q;
cin>>n>>q;
for(int i=1,x;i<=n;i++)
{
cin>>x;
nxt[i]=x;
par[x].insert(i);
}
for(int i=1;i<=n;i++)
{
if(!v1[i]) dfs(i);
}
mxh=ceil(log2(n));
up.assign(n+1,vector<int>(mxh+1,-1));
for(int x:latkav) dfs1(x,-1);
while(q--)
{
int start,end;
cin>>start>>end;
if(start==end) { cout<<"0\n"; continue; }
if(kai_cyc[start]!=-1)
{
if(kai_cyc[start]==kai_cyc[end])
{
int s=kyo_node[start];
int e=kyo_node[end];
int sz=cycle[kai_cyc[start]].size();
cout<<(s-e+sz)%sz<<"\n";
}
else { cout<<"-1\n"; }
continue;
}
if(isanc(end,start))
{
int jump=0;
for(int i=mxh;i>=0;i--)
{
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }
}
cout<<jump+1<<"\n";
}
else
{
int jump=0;
for(int i=mxh;i>=0;i--)
{
if(up[start][i]!=-1) { start=up[start][i]; jump+=1<<i;}
}
if(kai_cyc[start]==kai_cyc[end])
{
int s=kyo_node[start];
int e=kyo_node[end];
int sz=cycle[kai_cyc[start]].size();
cout<<((s-e+sz)%sz+jump)<<"\n";
}
else { cout<<"-1\n"; }
}
}
return 0;
}
I did not check if this is what you actually do in your code, but erasing one edge in every cycle is not correct: a node that is not on the cycle can reach all nodes on the cycle, but for some of them this may require passing over the erased edge.
I recently stumbled upon this problem. Found this blog helpful. My code (Tried to code as simple as possible)
...
One small doubt, why are we keeping a reverse graph, I cant understand the intuition behind that