Can anyone help me with this Graph problem?

I was solving this question:

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:

using namespace std;
int main()
    int t;
    while(t--) {
    	int n;
    	vector<int> adjlist[n];
    	int x1;
    	for(int i = 0;i < n;i++) {
       	int q;
       	while(q--) {
       		int dis[n];
       		for(int i = 0;i < n;i++) dis[i] = -1;
       		int x,y;
       		scanf("%d %d",&x,&y);
       		dis[x] = 0;
       		queue<int> bfs;
       		while(bfs.size() > 0) {
       			int node = bfs.front();
       			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;
       		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! :)

Also, what is your O(q) solution?

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

You can see the complete explanation here-
1 Like