### salt_n_ice's blog

By salt_n_ice, history, 3 years ago,

Problem : Link. I simply did bfs from node 1 and found the maximum distance from this node to all other nodes

Code

So the solution is O(n+m) but still, there is TLE in one case. Why?

• -2

| Write comment?
 » 3 years ago, # |   0 tried to do the same, got TLE on the LAST Test Case. Solved the problem with topological sort. Link to code https://cses.fi/paste/95851f6ac3e4e45919f087/
•  » » 3 years ago, # ^ |   0 Understood, thanks
•  » » 11 months ago, # ^ |   0
•  » » » 11 months ago, # ^ |   0 nice solution but I didnt understand few things like why we have to do toposort for 2 times and why you are not pushing it into the queue in topo function. Can you please explain your intuition and thought process that will be really helpful.Thanks in advance :)))
•  » » » » 11 months ago, # ^ |   0  You can solve it by using one toposort also.. (Accepted soln) ~~~~~ #include using namespace std; #define endl "\n" typedef long long ll; //------------------------Actual Code Starts Here----------- void dfs(ll node,vector&vis,vector>&g,stack&s){ vis[node]=1; for(auto child:g[node]){ if(vis[child]==0){ dfs(child,vis,g,s); } } s.push(node); } void solve(){ ll n,m;cin>>n>>m; vector>g(n+1) ; vectorvis(n+1,0); stacks; for(ll i=0;i>a>>b; g[a].push_back(b); } vectordis(n+1,-1e9); vectorpar(n+1,0); // do toposort(ohoho); for(ll i=1;i<=n;i++){ if(vis[i]==0){ dfs(i,vis,g,s); } } if(s.size()!=n){ cout<<"IMPOSSIBLE"<path; path.push_back(n); while(n!=1){ n=par[n]; path.push_back(n); } cout<=0;i--){ cout<>t; while(t--){ solve(); } return 0; } ~~~~~ 
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 https://cses.fi/paste/9ee3d2f988dc939e6047e1/ for this solution . Initially, we execute the toposort algorithm without considering node 1. Consequently, all nodes reachable from node 1 will have a parent value of -1. This is because we can reach these nodes from node 1, and node 1 is not included in our queue. Therefore, there is always at least one edge ensuring that the indegree for these nodes remains nonzero. In cases where the indegree is not zero, the parent value for these nodes is always set to -1.Towards the end of the process, we backtrack from node n to node 1 by following their parent relationships to determine the longest path. However, because we did not include node 1 in our initial queue, we will not reach any nodes that are reachable from node 1. To illustrate this point, consider the following example:10 103 9 6 5 6 9 2 8 4 8 1 2 7 10 7 6 7 5 8 10Without including node 1, the parent array appears as follows: -1 -1 -1 -1 -1 6 7 -1 -1 6 -1.Now, it's evident that node n is marked with -1, which indicates that there is either at least one path between node 1 and n or no path exists at all. If we execute toposort while including node 1, only nodes reachable from node 1 will have their parent values altered. The resulting parent array will look like this: -1 -1 1 -1 -1 6 7 -1 2 6 8.However, it's important to note that including node 1 in the initial toposort call does not guarantee that we will always be able to backtrack from node n to 1, as we do in this solution.
 » 21 month(s) ago, # | ← Rev. 2 →   0 I think test cases are weak in CSES for this problem.AC on Date: 13/09/2022 vector p[N]; void solve(){ ll n,m; cin>>n>>m; for(ll i=0;i>a>>b; --a,--b; p[a].pb(b); } vector dist(n,0); ll last[n]; for(ll i=0;i q; q.push(0); while(!q.empty()){ int x=q.top(); q.pop(); for(auto i:p[x]){ if((dist[x]+1)>dist[i]){ dist[i]=dist[x]+1; last[i]=x; q.push(i); } } } if(dist[n-1]==0){ cout<<"IMPOSSIBLE"< ans; // for(ll i=0;i
 » 11 months ago, # |   0 It is important to note that fraph is directed and doesnt contain any cycles, therefore the graph is DAG (Directed Acyclic Graph). Because of this, we can easily use dp on ths graph, but first we have to topologically sort the nodes.
 » 10 months ago, # | ← Rev. 2 →   0 Solved Using Topological Sort.
 » 5 months ago, # | ← Rev. 2 →   0 can anyone explain me why simple BFS gives TLE, and it seems O(n+m) but then what is the correct time complexity of the simple BFS solution?2) Complexitylease give a illustration of graph that shows O(m^2) complexity.
»
3 months ago, # |
0

Can anyone please suggest the error ? It is giving tle... ~~~~~

# include <bits/stdc++.h>

using namespace std;

# define int long long

signed main() { int n, m; cin >> n >> m; vector adj[n]; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u-1].push_back(v-1); } stackpq; vectordistance(n,0); //priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // int distance[n]; int parent[n]; for(int i=0;i<n;i++){ parent[i]=i; //distance[i]=0; } // distance[1] = 0; pq.push(0); while (!pq.empty()) { // int dis = pq.front().first; int node = pq.top(); pq.pop(); // if (dis > distance[node]) continue; // Skip if already processed for (auto i : adj[node]) { int adjnode = i; /// int adjdis = i; if (distance[adjnode] < distance[node] + 1) { distance[adjnode] = distance[node] + 1; pq.push(adjnode); parent[adjnode] = node; } } } if (distance[n-1] ==0) { cout << "IMPOSSIBLE" << endl; // return; } else { vector ans; int node = n-1; ans.push_back(node); while (node != 0) { // Change the stopping condition to node != 1 node = parent[node]; ans.push_back(node);
}

// ans.pop_back();
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for (auto it : ans) {
cout << it+1 << " ";
}
}
return 0;

}

~~~~~