Can anyone help me with this Graph problem?

I was solving this question: http://www.hackerearth.com/problem/algorithm/comrades-i-3/description/

My code is pretty straightforward. All I have used is a BFS from x to y. It is showing TLE. I don’t understand how to use DFS for this problem as the problem tag says so :stuck_out_tongue:

My code:

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
    	int n;
    	scanf("%d",&n);
    	vector<int> adjlist[n];
    	int x1;
    	for(int i = 0;i < n;i++) {
    		scanf("%d",&x1);
    		x1--;
    		adjlist[i].push_back(x1);
       	}
       	int q;
       	scanf("%d",&q);
       	while(q--) {
       		int dis[n];
       		for(int i = 0;i < n;i++) dis[i] = -1;
       		int x,y;
       		scanf("%d %d",&x,&y);
       		x--;y--;
       		dis[x] = 0;
       		queue<int> bfs;
       		bfs.push(x);
       		while(bfs.size() > 0) {
       			int node = bfs.front();
       			bfs.pop();
       			if(node == y) break;
       			int d = dis[node];
       			for(int i = 0;i < adjlist[node].size();i++) {
       				if(dis[adjlist[node].at(i)] == -1) {
       					dis[adjlist[node].at(i)] = d+1;
       					bfs.push(adjlist[node].at(i));
       				}
       			}
       		}
       		if(dis[y] == -1) printf("%d\n",dis[y]);
       		else printf("%d\n",dis[y]-1);
       	}
    }
    return 0;
}
1 Like
Your code is absolutely correct my friend. Its just that you your complexity in O(n*q)
With n and q being upto 10^5 you are running 10^10 iterations

U can run like 10^8 iterations and get AC

Try optimising your approach to something like O(qlogn)
But as I see there is an O(q) solution to this problem.

Happy coding! :)
You can see the complete explanation here-
http://www.hackerearth.com/problem/algorithm/comrades-i-3/editorial/
1 Like

Can you help me optimise it? Why would I post it in the forums then? o.0

Also, what is your O(q) solution?