CCDSAP Notes.txt

1. PQ
	non incresing order(By default max heap)
	.size()
	.empty()
	.push()
	.pop()
	.top()
	for min heap :- multiply values by -1

2. stack and queue .. push and pop .. .top() .. .front() .. .back()

3. For Your UFDS code ... Convert the nodes w.r.t 0 based indexing ... If there's a connection between 1 and 2 .. Make it 0 and 1
---------------------------------------------------
#include <climits>
INT_MIN

Around 10^7 operations are allowed per second .. So decide accordingly .. For 10^6 operations .. You can go for O(n) then..

cout<<fixed<<setprecision(4)<<ans<<endl;

---------------------------------------------------
4. Segment Tree - Keep size of the tree as 4*n

5. DFS/BFS

Transitive Closure - Matrix which shows which node can be reached by which node
Connected Components - Sepeare Subgraphs

6. MSP

Kruskal -- select the edges with least weight such that it doesn't create a cycle
Prim -- Start from the source keep connecting edge with least weight such that it doesn't create a cycle

7. Topological Sort

Do DFS and keep on adding nodes to the stack when coming back from the calls .. In the end print the contents of the stack .. Topological sort can have many order's .. In each order if there is an edge from u to v .. u should come before v in the sequence

8. Euler Path

All Edges are visited exactly once .. Here , all non zero degree vertices should be connected and All should be having even degree

9. Strongly Connected Components

Can go from one node to all other nodes
Kosaraju -- Apply dfs and when a node is finished(no unvisited neighbours) add it in stack .. reverse all the connections and pop the nodes and apply dfs .. The nodes that can be visited by keeping the popped node as source are all strongly connected.