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?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Problem : Link. I simply did bfs from node 1 and found the maximum distance from this node to all other nodes
const int INF = 1e9;
const int sz = 1e5+1;
int n,m;
vector<int> last(sz);
vector<vector<int> > adj(sz);
vector<int> d(sz,0);
void solve()
{
cin>>n>>m;
for(int i=0; i<m; ++i)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);
}
queue<int> q;
q.push(1);
while(!q.empty())
{
int s = q.front();
q.pop();
for(auto u : adj[s])
{
if(d[s]+1>d[u])
{
d[u]=1+d[s];
last[u]=s;
q.push(u);
}
}
}
if(d[n]==0)
{
cout<<"IMPOSSIBLE"<<endl;
return;
}
vector<int> ans;
int k=n;
while(k!=1)
{
ans.push_back(k);
k=last[k];
}
ans.push_back(1);
reverse(ans.begin(), ans.end());
cout<<1+d[n]<<endl;
for(int i=0; i<ans.size(); ++i)
cout<<ans[i]<<" ";
cout<<endl;
}
int main()
{
solve();
}
So the solution is O(n+m) but still, there is TLE in one case. Why?
Name |
---|
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/
Understood, thanks
https://cses.fi/paste/9ee3d2f988dc939e6047e1/ :New
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 :)))
` You can solve it by using one toposort also.. (Accepted soln) ~~~~~
`
I think test cases are weak in CSES for this problem.
AC on Date: 13/09/2022
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.
Why toposort? And hwy is it giving TLE
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.
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);
}
}
~~~~~
The solution isn't O(n+m). The worst case would be O((n+m)^2).
can anybody please tell the intuition behind the topo sort.