striver79/striversgraphseries

striversgraphseries's Issues

you are adding the same nodes with with different key values in the queue

try using if(mst[x]==true){continue;}
in this starting of the last while loop

Wrong link to the NOTES in take u forward

The link to the DFS in the Introduction to Graph section of this series in take u forward is incorrect: URL: https://takeuforward.org/graph/striver-graph-series-top-graph-interview-questions/

The link leads to the Introduction to DP. Please update it to https://takeuforward.org/data-structure/depth-first-search-dfs/.

I didn't find a report of an issue on the site itself, so I added it here.

Semicolon mistake!!

StriversGraphSeries/topoSortCppBFS

Line 20 in 6e18e99

vector<int> topo

It gives Tle, but Sets doesn't

I tried this algorithm on problem : https://cses.fi/problemset/task/1671/
It gives TLE with this code, but when i did using the sets and erasing the useless nodes, it got accepted.
TLE CODE:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p32;
const ll mod = 1000000007;
vector<vector<pair<ll, ll>>> edges;
ll n, m;

void dijsktra() {
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;// min-heap ; In pair => (dist,from)
vector distTo(n+1,LLONG_MAX); // 1-indexed array for calculating shortest paths;

distTo[1] = 0;
pq.push(make_pair(0,1));	// (dist,from)

while( !pq.empty() ){
	ll dist = pq.top().first;
	ll prev = pq.top().second;
	pq.pop();
	
	vector<pair<ll,ll> >::iterator it;
	for( auto it : edges[prev]){
		ll next = it.first;
		ll nextDist = it.second;
		if( distTo[next] > distTo[prev] + nextDist){
			distTo[next] = distTo[prev] + nextDist;
			pq.push(make_pair(distTo[next], next));
		}
	}
	
}

for(int i = 1 ; i<=n ; i++)	cout << distTo[i] << " ";
cout << "\n";

}
void solve() {
cin>>n>>m;
edges.resize(n+1);
for(ll i=0; i<m; i++) {
ll s, d, w;
scanf("%lld %lld %lld", &s, &d, &w);
edges[s].push_back(make_pair(d, w));
}
dijsktra();
}

void init_code() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int main() {

init_code();

ll t;
t = 1;
while(t--) {
	solve();
}
return 0;

}

Accepted CODE using SETS:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p32;
const ll mod = 1000000007;
vector<vector<pair<ll, ll>>> edges;
ll n, m;

void dijsktra() {
set<pair<ll, ll>> setds; // for getting node in ascending order of their weight till now.
vector dist(n+1, LLONG_MAX);

dist[1] = 0;     // starting from node 1.
setds.insert(make_pair(0, 1));

while(!setds.empty()) {
	pair<ll, ll> minWeightNode = (*setds.begin());

	for(auto child : edges[minWeightNode.second]) {
		ll node = child.first;
		ll w = child.second;
		ll tillDist = minWeightNode.first + w;

		if(tillDist < dist[node]) {
			if(dist[node] != LLONG_MAX) {
				setds.erase(make_pair(dist[node], node));
			}
			dist[node] = tillDist; 	 
			setds.insert(make_pair(tillDist, node));
		}
	}
	setds.erase((*setds.begin()));
}

for(ll i=1; i<=n; i++) printf("%lld ", dist[i]);

}
void solve() {
cin>>n>>m;
edges.resize(n+1);
for(ll i=0; i<m; i++) {
ll s, d, w;
scanf("%lld %lld %lld", &s, &d, &w);
edges[s].push_back(make_pair(d, w));
}
dijsktra();
}

void init_code() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int main() {

init_code();

ll t;
// cin>>t;
t = 1;
while(t--) {
	solve();
}
return 0;

}

Checking for dist[it.u] != INF in Bellman Ford Algo

Don't we have to check for dist[it.u] != INF before adding it.wt. Because if we have negative weight this will become less to INF, and can change the dist[it.v]?
like code may be :

for(int i = 1;i<=N-1;i++) { for(auto it: edges) { if(dist[it.u] != INF && (dist[it.u] + it.wt) < dist[it.v]) { dist[it.v] = dist[it.u] + it.wt; } } }

dependencies

it doesnt have import java.util.*; which is used to import arraylist

One if condition is missing from Prims Efficient solution

The given solution is breaking for the following test case on gfg
10 11
0 1 7
0 4 4
0 7 8
0 9 3
1 7 7
1 8 3
2 5 8
2 7 10
3 4 3
4 6 10
5 7 8

Typo in java code of shortest path of undirected graph

there is a little mistake in the java code on line number 20 in file shortestPathUndirectedUnweightedGraphJava it should be adj.get(node) instead of adj.get(u)

parents[] in Solution class.

Hello Bhaiya,
What is the use of parent[] in solution class.

C++AdjacencyListRepresentation

I guess it should be vector<int> adj[n+1] instead vector<vector<int>> adj[n+1].
In video it was correct.

Worst Case Complexity Of efficient- Heap Solution will be greater than N^2

//***********************Following Code Can have time Complexity > N^2-------------------
for (auto it : adj[u]) {
int v = it.first;
int weight = it.second;
if (mstSet[v] == false && weight < key[v]) {
parent[v] = u;
key[v] = weight;
pq.push({key[v], v});
}
}

---

Above Code will keep pushing every weight and node if every time weight from the current node(that is 'u') is less than the weight previous.

So Let assume I have a weightage Complete graph, And We are Starting From Node 0, then for every last chosen MST NODE( that is 'u') => there will be K push operation in the priority queue, where K denotes no of node remaining from MST;

Initial priority Queue will have {{0,0}}

pop {0,0} from priority queue,
Put Node 0 in MST of Weight 0
Run Loop for child of NODE 0
->priority queue will push {1,1} { 5,2} {5,3}

Priority queue become {{1,1} { 5,2} {5,3}}

now it will pop {1,1}
Put Node 1 in MST of weight 1
Run Loop for child of NODE 1
->pq.push-> {3,2} {4,3}
Priority queue become {{5,2},{5,3},{3,2} ,{4,3}}

now it will pop {3,2}
put Node 2 in MST of weight 3
Run Loop for child of NODE 2
-> pq.push->{2,3}
Priority queue become {{5,2},{5,3},{4,3},{2,3}}

now it will pop {2,3}
push Node 3 in MST of Weight 2
Run Loop for child of NODE 3
-> No Push Operation
Priority queue become {{5,2},{5,3},{4,3}}

Now there will be an only pop operation that is 3-times pop then while(!pq. empty()) break out because priority queue becomes empty.

---

Now Generalizing Time complexity of above example for N Node.
So If we consider N Node Complete Graph such that for every new MST Node we will get the minimum distance for all remaining Node then
iteration 1 -> Push N-1 item in priority queues and Initial size of Priority Queue was 0
POP Minimum, Size become N-2
iteration 2 -> Push N-2 item in priority queues and Initial size of Priority Queue was N-2;
POP Minimum, Size become N-2+N-2-1=>2N-5;
iteration 3-> Push N-3 item in priority queues and Initial size of Priority Queue was 2N-5;
POP Minimum, Size become 2N-5+N-3-1=>3N-9;
iteration 4-> Push N-4 item in priority queues and Initial size of Priority Queue was 3N-9;
POP Minimum, Size become 3N-9+N-4-1=>4N-14;

.....So on till N-1 Iteration AtMax.

*****Push/pop of single element Time Complexity Of Priority Queue is LogN ************
computing Time Complexity of priority queue push operation from iteration 2
Time Complexity = (N-2)log(N-2)+ (N-3)log(2N-5)+ (N-4)log(3N-9)+ (N-5)log(4N-14) ..... + (1)log(NN-(N(N+3)/2)).

Now when we have all nodes visited in MST, then we will have an only Pop operation, Priority Queue will have NN-(N(N+3)/2) at last so Time Complexity will be poping all element NN-(N(N+3)/2) log( NN-(N(N+3)/2)).

So Overall Time Complexity will be Push Time Complexity+ Popping at End Complexity, Conclusion If We Solve Above Equation it Seems Like Time Complexity N^2 OR >N^2.

If I Did any mistake then let me know, But Please Dry Run Time Complexity for above shown Test Case, Sorry if I made any mistake
I hope u understood my doubt.