--------------------↵
↵
Vertices,edges,undirected and directed graph,cyclic & acyclic graph,degree indegree & outdegree and weights.↵
In an undirected graph, the sum of degrees of all vertices is double the the no. of edges (We consider degree=indegree=outdegree in an undirected graph).↵
↵
Graph representation in C++↵
--------------------↵
Let us say there are n nodes and m edges. And adj[i][j] represents there is an edge from node i to j.↵
↵
There are two ways to represent a graph↵
↵
↵
#### 1. Adjacency matrix:↵
↵
↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
int n, m;↵
cin >> n >> m; ↵
int adj[n+1][n+1]; //1 based indexing ↵
for(int i = 0;i<m;i++) {↵
int u, v; ↵
cin >> u >> v;↵
adj[u][v] = 1; ↵
adj[v][u] = 1; //write this line only if the graph is undirected ↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity:**O(m)↵
**Space Complexity:**O(n*n)**↵
↵
↵
↵
#### 2. Adjacency List↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
int n,m;↵
cin >> n >> m; ↵
vector<vector<int> > adj(n+1); ↵
for(int i = 0;i<m;i++) {↵
int u, v; ↵
cin >> u >> v;↵
adj[u].push_back(v); ↵
adj[v].push_back(u); //undirected graph↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity:**O(m)↵
**Space Complexity:**O(n*n)↵
↵
If there are also weights in edges, we create the adjacency list as ' vector <vector < pair <int,int> > > ' where first value is node(v) and second value represents weight b/w the nodes(u and v).↵
↵
Since there can be multiple disconnected components in a graph, while graph traversal we have to call BFS/DFS from every unvisited node. To avoid repetition we store information if a node is visited or not by creating a boolean array where is_visited[i]==true represents node 'i' is visited.↵
↵
~~~~~↵
for(int i=1i<=n;i++)↵
{↵
if(!is_visited[i]) BFS(i);↵
}↵
~~~~~↵
↵
↵
BFS↵
---↵
Just after pushing a node in queue,make vis[node]=true;↵
Why we do vis[node]=true just after pushing the node in queue and not just after we pop it out of queue?↵
Because let say a node has two parents (possible in cyclic graph then it will be pushed in queue twice so we do vis[child]=1 on first encounter of the node so that on next encounter it is not pushed again.)↵
↵
<spoiler summary="code">↵
~~~~~↵
for(int i=0;i<n;i++)↵
{↵
if(!vis[i])↵
{↵
queue<int> q; ↵
q.push(i); ↵
vis[i] = 1; ↵
while(!q.empty()) ↵
{↵
int node = q.front();↵
q.pop();↵
cout<<node<<" "; ↵
for(auto child : adj[node]) ↵
{↵
if(!vis[child]) ↵
{↵
q.push(child);↵
vis[child] = 1; ↵
}↵
}↵
}↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)↵
↵
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for queue )↵
↵
DFS↵
---↵
why we do vis[node]=1 in startint or DFS fn and not do vis[child]=1 just like BFs?↵
↵
Because then vis[source_node] will never become 1.Otherwise it is same only.↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
void dfs(int node, vector<bool> &vis,vector <vector <int> > &adj) ↵
{↵
cout<<node<<" "; ↵
vis[node]=1; ↵
for(auto child : adj[node]) ↵
{↵
if(!vis[child]) ↵
{↵
dfs(child,vis,adj); ↵
}↵
}↵
}↵
↵
//Inside main()↵
for(int i = 1;i<=V;i++) ↵
{↵
if(!vis[i]) ↵
dfs(i, vis, adj); ↵
}↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)↵
↵
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for stack space )↵
↵
↵
↵
↵
Cycle Detection in Graphs↵
---↵
↵
#### Case 1: Cycle detection in undirected graph using dfs↵
↵
Since by definition, in an undirected graph, a cycle has at least three nodes,so we will need to store the parent of the node as well.↵
If a node adjacent to a node ( that is not its parent node ) is already visited, the component contains a cycle.↵
↵
<spoiler summary="code">↵
~~~~~↵
bool checkForCycle_DFS(int node, int parent, vector<int> &vis, vector <vector<int> > &adj) ↵
{↵
vis[node] = 1; ↵
for(auto child:adj[node])↵
{↵
if(vis[child]&&child!=parent) return true; ↵
if(!vis[child]) ↵
{↵
if(checkForCycle_DFS(child, node, vis, adj)) return true; ↵
}↵
↵
}↵
↵
return false; ↵
}↵
↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i])↵
{↵
if(checkForCycle_DFS(i, -1, vis, adj)) return true; ↵
}↵
↵
}↵
return false; ↵
~~~~~↵
</spoiler>↵
↵
#### Case 2:Cycle detection in the undirected graph using BFS↵
-------------↵
↵
<spoiler summary="code">↵
~~~~~↵
checkCycle_BFS(int node, int parent, vector<bool> &vis, vector <vector<int> > &adj)↵
{↵
vis[i]=1; ↵
queue<pair <int,int> > q; ↵
q.push({i,-1}); ↵
while(!q.empty()) ↵
{↵
int node = q.front().first;↵
int parent=q.front().second;↵
q.pop();↵
for(auto child : adj[node]) ↵
{↵
if(vis[child]&&child!=parent) return true;↵
if(!vis[child]) ↵
{↵
q.push({child,node});↵
vis[child] = 1; ↵
}↵
}↵
}↵
return false;↵
}↵
↵
//Inside main()↵
for(int i=0;i<n;i++)↵
{↵
if(!vis[i])↵
{↵
if(checkCycle_BFS(i,-1,vis,adj)) return true;↵
}↵
}↵
return false;↵
↵
~~~~~↵
</spoiler>↵
↵
#### Case 3:Cycle detection in the Directed graph using DFS-↵
↵
Think why color-coding of the graph is required in cycle detection in an undirected graph and why information about the parent of the node is not needed.↵
↵
<spoiler summary="code">↵
~~~~~↵
bool checkForCycle_DFS(int node, vector<int> &color, vector <vector<int> > &adj) ↵
{↵
color[node] = 1; ↵
for(auto child:adj[node])↵
{↵
if(color[child]==1) return true; ↵
if(!color[child]) ↵
{↵
if(checkForCycle_DFS(child,color, adj)) return true; ↵
}↵
↵
}↵
color[node]=2;↵
return false; ↵
}↵
↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i])↵
{↵
if(checkForCycle_DFS(i,vis, adj)) return true; ↵
}↵
↵
}↵
return false; ↵
~~~~~↵
</spoiler>↵
↵
#### Case 4:Cycle detection in the Directed graph using BFS↵
↵
Assume the directed graph to be acyclic i.e. DAG and find its topological order.If we can do topological sorting i.e. pushing all nodes in queue , the graph is acyclic,other wise it is cyclic.↵
↵
We increase our count by 1 (starting from 0) each time we push a node in queue. And if final value of count==no. of nodes in graph, the graph is a DAG.↵
↵
<spoiler summary="code">↵
~~~~~↵
//The given code is for one component graph. ↵
//You can find topological order for multiple component graph using vis array.↵
↵
bool isCyclic(int N, vector<int> adj[]) ↵
{↵
queue <int> q; ↵
vector <int> indegree(N, 0);↵
↵
for(int i = 0;i<N;i++) ↵
{↵
for(auto it: adj[i])↵
indegree[it]++; ↵
}↵
↵
for(int i = 0;i<N;i++) ↵
{↵
if(indegree[i] == 0) ↵
q.push(i); ↵
}↵
↵
int cnt = 0;↵
while(!q.empty()) ↵
{↵
int node = q.front(); ↵
q.pop();↵
cnt++;↵
for(auto it : adj[node]) ↵
{↵
indegree[it]--;↵
↵
if(indegree[it] == 0) ↵
q.push(it)↵
}; ↵
↵
} ↵
if(cnt == N) return false; ↵
return true;↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
Bipartite graph:↵
-------↵
↵
A graph will never be bipartite if it has a cycle with odd no. of nodes and if a graph has no cylces with odd no. of nodes, then it must be bipartite.↵
↵
#### Check whether a graph is bipartite or not using BFS↵
↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
bool bipartiteBFS(int src, vector <vector<int> > &adj, int color[]) ↵
{↵
color[src] = 1;↵
↵
queue<int> q;↵
q.push(src); ↵
↵
while(!q.empty()) ↵
{↵
int node = q.front(); ↵
q.pop();↵
↵
for(auto child : adj[node]) ↵
{↵
if(color[child] == color[node]) ↵
{↵
return false; ↵
}↵
else if(color[child] == -1) ↵
{↵
color[child] = 1 - color[node]; ↵
q.push(child); ↵
}↵
}↵
}↵
return true; ↵
}↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{ ↵
if(color[i] == -1) ↵
{↵
if(!bipartiteBFS(i, adj, color)) return false;↵
}↵
}↵
return true; ↵
~~~~~↵
</spoiler>↵
↵
↵
#### Check whether a graph is bipartite or not using DFS↵
↵
<spoiler summary="code">↵
~~~~~↵
bool bipartiteDfs(int node, vector <vector<int> > &adj, int color[]) ↵
{↵
for(auto child : adj[node]) ↵
{↵
↵
if(color[child] == color[node]) return false; ↵
else if(color[child] == -1) ↵
{↵
color[child] = 1 - color[node];↵
if(!bipartiteDfs(child, adj, color)) ↵
{↵
return false; ↵
}↵
}↵
}↵
return true; ↵
}↵
↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(color[i] == -1) ↵
{↵
color[i] = 1;↵
if(bipartiteDfs(i, adj, color)==false) return false;↵
} ↵
}↵
return true; ↵
~~~~~↵
</spoiler>↵
↵
↵
Topological Sorting:↵
--------↵
↵
Only possible in DAG. It is a linear order of vertices such that for every directed edge u-->v, vertex u comes before v in that order. A DAG has at least one node with indegree=0.↵
↵
#### Topological sorting using BFS↵
↵
First, calculate indegree of all nodes and store it in vector.Then push all nodes with degree==0 in a queue.Take each node one by one out of queue and for all its child ,decrease their indegree by 1. After this if any child has indegree==0, push them in the queue.↵
↵
<spoiler summary="code">↵
~~~~~↵
//The given code is for one component graph. ↵
//You can find topological order for multiple component graph by calling this func for every unvisited node.↵
↵
vector<int> findTopo(int N,vector < vector <int> > &adj) ↵
{↵
vector<int> indegree(N, 0);↵
↵
for(int i = 0;i<N;i++)↵
for(auto it: adj[i]) ↵
indegree[it]++; ↵
↵
queue<int> q; ↵
for(int i = 0;i<N;i++) ↵
{↵
if(indegree[i] == 0) q.push(i); ↵
}↵
↵
vector<int> topo;↵
↵
while(!q.empty()) ↵
{↵
int node = q.front(); ↵
q.pop(); ↵
topo.push_back(node)↵
for(auto child : adj[node]) ↵
{↵
indegree[child]--;↵
↵
if(indegree[child] == 0)↵
q.push(child); ↵
↵
}↵
}↵
return topo;↵
}↵
~~~~~↵
</spoiler>↵
↵
#### Topological sorting using DFS↵
↵
Topological order is the order of nodes in decreasing order of finishing time i.e. the node that gets finished at last comes first in order.↵
↵
<spoiler summary="code">↵
~~~~~↵
//The given code is for one component graph. ↵
//You can find topological order for multiple component graph by calling this func for every unvisited node.↵
↵
void findTopoSort(int node, vector<int> &vis, stack<int> &st, vector<int> adj[])↵
{↵
vis[node] = 1; ↵
for(auto it : adj[node]) ↵
{↵
if(!vis[it]) ↵
findTopoSort(it, vis, st, adj); ↵
}↵
st.push(node); ↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
Shortest path algorithms:↵
------------------↵
↵
#### Shortest path of all nodes from a node in a unweighted/0-1 weighted graph.↵
↵
Use BFS for this because BFS visits nodes in a sequential manner. That is nodes at the same level are visited simultaneously.↵
Run BFS and equate dist[node] = 1+dist[parent].↵
↵
BFS can also be used to find shortest path in 0-1 weighted graph.Instead of using queue,use deque and if weight(node-->child)==0,push at front else at back of deque.↵
BFS can be used to make different binary string using this 0-1 trick. (e.g. in https://www.spoj.com/problems/ONEZERO)↵
↵
<spoiler summary="code">↵
~~~~~↵
void BFS(vector<int> adj[], int N, int src) ↵
{ ↵
int dist[N];↵
dist[src] = 0;↵
for(int i = 1;i<N;i++) dist[i] = INT_MAX; ↵
↵
queue<int> q;↵
q.push(src); ↵
↵
while(q.empty()==false) ↵
{ ↵
int node = q.front(); ↵
q.pop();↵
↵
for(auto it:adj[node])↵
{↵
//no use of vis array because if a dist[node] is relaxed from INT_MAX,↵
//it implies it is being visited first time.↵
if(dist[it]==INT_MAX)↵
{↵
dist[it]=dist[node]+1;↵
q.push(it);↵
}↵
} ↵
} ↵
for(int i = 0;i<N;i++) cout << dist[i] << " "; ↵
↵
} ↵
~~~~~↵
</spoiler>↵
↵
#### Shortest path of all nodes from a node in a weighted DAG ↵
↵
The weights can be -ve.↵
↵
Minimum sum to reach a node 'v' i.e. dist[v] is minimum of all (dist[u]+weight(u-->v)),where u is node from all its parents.↵
Similarly, dist[u] is calculated with the help of its parents.We can observe that ultimately we have to start calculating dist[] from source node and in topological order ,we have to visit the nodes↵
↵
We visit nodes in topological order and relax all its children. In this way, each node is relaxed by all its parents.↵
↵
<spoiler summary="code">↵
~~~~~↵
void shortestPath(int src, int N, vector<pair<int,int>> &adj) ↵
{ ↵
int vis[N] = {0};↵
stack<int> st; ↵
for (int i = 0; i < N; i++) ↵
if(!vis[i]) ↵
findTopoSort(i, vis, st, adj); ↵
↵
int dist[N]; ↵
for (int i = 0; i < N; i++) ↵
dist[i] = 1e9; ↵
dist[src] = 0; ↵
↵
while(!st.empty()) ↵
{ ↵
int node = st.top(); ↵
st.pop(); ↵
↵
if (dist[node] != INF) ↵
{↵
for(auto child : adj[node]) ↵
{↵
if(dist[node] + child.second < dist[child.first]) ↵
dist[child.first] = dist[node] + child.second; ↵
}↵
}↵
} ↵
↵
for (int i = 0; i < N; i++) ↵
(dist[i] == 1e9)? cout<< "INF ": cout << dist[i] << " "; ↵
} ↵
~~~~~↵
</spoiler>↵
↵
#### Shortest path in +ve weighted graph.↵
↵
Dijkstra's algorithm is basically an efficient version of breadth-first search on a different graph.↵
↵
Given a graph G with positive integer edge-weights, one could construct a new unweighted graph H, by replacing each weighted edge with a number of edges equivalent to its weight. So, for example, if you had an edge (u,v) with weight 10 in G, you'd replace this edge with a series of 10 edges between u and v.↵
↵
Since BFS visits nodes in increasing order of their level (distance from source node) i.e. at any point of time,if a node n1 level is smaller than node n2, minimum distance from n1 will be calculated earlier than n2. ↵
↵
From this, we get an intuition that at any point of time, calculate minimum distance of children of that node which is nearest to the source node. This is a kind of greedy approach because we are relaxing children of that node which is **locally**(at a point of time) nearest to the source.↵
↵
Since min_priority_queue always stores elements in increasing order,we will use it.We can also use set instead of it.↵
↵
<spoiler summary="code">↵
~~~~~↵
typedef pair<int, int> pi;↵
↵
vector <int> dijkstra(int n,vector<vector<pi>> &adj, int s)↵
{↵
priority_queue<pi, vector<pi>, greater<pi> > pq;↵
//min heap (weight,node)↵
↵
vector <int> dist(n);↵
for(int i=0; i<n; i++) dist[i]=1e9;↵
dist[s]=0;↵
↵
pq.push({dist[s], s});↵
↵
while (!pq.empty())↵
{↵
int u=pq.top().second;↵
pq.pop();↵
↵
for(auto p: adj[u])↵
{↵
int v=p.first;↵
int w=p.second;↵
if(dist[u] + w < dist[v]) ↵
{↵
dist[v] =dist[u] + w;↵
pq.push({dist[v], v});↵
}↵
}↵
↵
}↵
↵
return dist;↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
**Why Dijkstra doesn't work with -ve weights:**↵
↵
If all weights are non-negative, adding an edge can never make a path shorter but this is not valid if edge weight is -ve.Dry run a case to explain it further.↵
↵
Time Complexity:O((E+V)*logV) ↵
Space Complexity:O(V)↵
↵
#### Bellman Ford ↵
↵
Since the negative weighted cycle has sum — infinity, Bellman-Ford works in a directed graph iff the graph has no -ve weighted cycle and works in an undirected graph iff all weights are non -ve.↵
↵
Relax all edges n-1 times.Why exactly n-1 times.Since in each relaxation,in worst case,only one node will get relaxed and maximum distance of a node from source node is n-1.↵
Consider example 1-->2-->3-->4-->5. First 5 is relaxed,then 4 and so on till 2 ,n-1 times.↵
↵
Bellman Ford can also be used to detect -ve cycle in a graph.First relax all edges n-1 times.Then relax one more time.If any vertex is relaxed,then graph contains -ve cycle.↵
↵
<spoiler summary="code">↵
~~~~~↵
// dp[i] = shortest distance to node i↵
// dp[i] = INFINITY for all↵
↵
dp[s]= 0 ;↵
for ( int i= 1 ; i<=n -1 ; i++)↵
{↵
for ( auto e: edges)↵
{↵
int u=e.first;↵
int v=e.second.first;↵
int w=e.second.second;↵
↵
if (dp[u]+w <dp[v])↵
dp[v]=dp[u]+w;↵
↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
#### Floyd Warshall Algo:↵
↵
It gives the shortest distance b/w any two nodes.↵
↵
**Iterative DP code:**↵
↵
<spoiler summary="code">↵
~~~~~↵
void shortest_distance(vector<vector<int>>&weight)↵
{↵
int n=weight.size();↵
for(int k=0;k<n;k++)↵
{↵
for(int i=0;i<n;i++)↵
{↵
for(int j=0;j<n;j++)↵
{↵
if(i==j) dist[i][j]==0;↵
else↵
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);↵
}↵
}↵
}↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity:** :O(V*V*V)↵
↵
DSU↵
-----↵
↵
It is a data structure used to perform the union of disjoint sets efficiently.Each node in the set has parent.↵
↵
Representative node:Topmost node of a set whose parent is the node itself.↵
↵
**Naive Implementation:**↵
↵
<spoiler summary="code">↵
~~~~~↵
void make_set ( int n)↵
{↵
for ( int i= 0 ; i<n; i++)↵
{↵
par[i]=i;↵
}↵
}↵
↵
int find_set (int x)↵
{↵
if ( par[x] == x)↵
return x;↵
↵
return find_set(par[x]);↵
}↵
↵
int union_set(int a,int b)↵
{↵
int p1=find_set(a),p2=find_set(b);↵
//ensuring both nodes are not belonging to same set↵
if(p1!=p2)↵
par[p1]=p2;↵
}↵
~~~~~↵
</spoiler>↵
↵
Time complexity:O(n) for make_set and O(d) for find_set() and union_set() where d=maximum depth possible of a node.↵
↵
To reduce time complexity of find_set() and union_set(),we have to decrease depth.This can be possible if a parent has maximum children possible.↵
↵
We can do this by doing modification in find_set() and union_set():↵
↵
For finding representative node a node using find_set(), we will be traversing to its parent, grandfather and so on... . While traversing, we make a representative node,the parent of each node traversed.↵
↵
While merging two sets, we make the smaller-sized set child of the larger-sized set to ensure minimum depth. (visualize why so, by a diagram). To know the size of the set, we have to maintain an array ,where rnk[i] tells the size of the set treating 'i' as representative node.↵
↵
<spoiler summary="code">↵
~~~~~↵
void make_set (int n)↵
{↵
for (int i= 0 ; i<n; i++)↵
{↵
par[i] = i;↵
rnk[i] = 1 ;↵
}↵
}↵
↵
//While traversing ,we make representative node ,the parent of each node traversed.↵
int find_set ( int x)↵
{↵
if ( par[x] == x)↵
return x;↵
↵
par[x]=find_set(par[x]);↵
return par[x];↵
}↵
↵
void union_set ( int a, int b)↵
{↵
int p1 = find_set(a);↵
int p2 = find_set(b);↵
↵
if ( p1 == p2)↵
return ;↵
↵
if (rnk[p1] > rnk[p2])↵
{↵
par[p2]=p1;↵
rnk[p1] = rnk[p1] + rnk[p2];↵
}↵
↵
else↵
{↵
par[p1] = p2;↵
rnk[p2] = rnk[p1] + rnk[p2];↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time complexity** :O(1)↵
↵
↵
↵
( Using path compression in find_set() alone reduces time complexity to O (log N)approximately. And time Complexity of find_set() and union_set(), when you use both path compression and union by rank: O( α(N) ) where α(N) = Inverse Ackermann Function which is approximately equal to O(1). )↵
↵
**3 Applications of DSU**↵
↵
1.Finding the number of components in a graph↵
↵
2. Finding MST↵
↵
3.Finding a cycle in undirected graph↵
↵
<spoiler summary="code">↵
~~~~~↵
make_set(n);↵
for( auto e: edges)↵
{↵
int u=e.first;↵
int v=e.second;↵
if ( find_set(u) == find_set(v) )↵
{↵
cout<<"Cycle found";↵
break;↵
}↵
union_set(u,v);↵
}↵
~~~~~↵
</spoiler>↵
↵
Minimum Spanning Tree:↵
---------------↵
↵
A spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. Thus it has n nodes and n-1 edges. A single graph can have many different spanning trees. ↵
↵
A minimum spanning tree (MST) for a weighted, connected, undirected graph is a spanning tree with sum of the weight of its all edges is less than or equal to the weight of every other spanning tree.↵
↵
####Prim's Algo to find MST:↵
↵
We will start from an empty mstSet and keep adding nodes till no. of nodes in mstSet=n. At any particular time,we will select that node from the children of all nodes already included in MST, whose edge formed will have minimum weight among all possible edges.↵
↵
This is a greedy approach because we are adding node in a sequence such that it gives least possible weight locally.↵
↵
**Implementation: **We will take a boolean vector mst to know which node is already included in mst.A int vector 'key',where key[node] stores minimum weight of among all possible edges made by node with its parent. Whenever a new node is inserted, for all children of it,we will↵
update key[child] if weight(node-->child)< key[child].We will insert child in priority queue only if the child has that node as minimum weighted edge among all its parents.We will also store parent[node] to print MST in future.↵
↵
↵
**Naive Implementation:** ↵
Finding minimum of key[node] values among all nodes will take O(n) time therefore, TC=O(n*n).↵
↵
**Optimal**↵
We will store {key[node],node} of all nodes in a priority queue so that node with minimum key[node] can be popped out in O(logn) time. ↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
↵
vector <bool> mst(n,0);↵
vector <int> key(n,INT_MAX);↵
↵
//pii= pair<int,int>↵
priority_queue <pii,vector<pii>,greater <pii> > pq;↵
↵
//pq.top().first=key[node] (minimum) , pq.top().second=node↵
↵
key[0]=0;↵
pq.push({0,0});↵
parent[0]=-1;↵
↵
// Instead of counting till n-1,run the loop till all the nodes have been visited↵
// because here we simply take the minimal from the priority queue, so a lot of times a node might be taken twice↵
// hence its better to keep running till all the nodes have been taken. ↵
// try the following case: ↵
// 6 7 ↵
// 0 1 5 ↵
// 0 2 10 ↵
// 0 3 100 ↵
// 1 3 50 ↵
// 1 4 200↵
// 3 4 250↵
// 4 5 50 ↵
↵
while(!pq.empty())↵
{↵
int u=pq.top().second;↵
pq.pop();↵
↵
↵
mst[u]=true;↵
↵
//since 'u' is a newly inserted node,finding which child of will make minimum weighted edge↵
for(auto child:adj[u])↵
{↵
int v=child.first;↵
int w=child.second;↵
if(!mst[v]&&key[v]>w)↵
{↵
key[v]=w;↵
pq.push({key[v],v});↵
//if v is picked,we should know its parent↵
par[v]=u;↵
}↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity: **O(nlogn)↵
↵
#### Kruskal's Algo to find MST:↵
↵
**Using Greedy+DSU :** ↵
Sort all edges in increasing order and keep including the edge only if the edge is not making a cycle.↵
This is greedy approach because we are trying to make globally minimum weight by selecting locally minimum weighted edge.To join to edges ,we use DSU operations,union_set and find_set.↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
struct node ↵
{↵
int u,v,w; ↵
node(int first, int second, int weight) ↵
{↵
u = first,v = second, wt = weight;↵
}↵
};↵
↵
bool comp(node a, node b) ↵
{↵
return a.wt < b.wt; ↵
}↵
↵
int find_set(int u, vector<int> &parent) ↵
{↵
if(u == parent[u]) return u; ↵
return parent[u] = find_set(parent[u], parent); ↵
}↵
↵
void union_set(int u, int v, vector<int> &parent, vector<int> &rank) ↵
{↵
u = find_set(u, parent);↵
v = find_set(v, parent);↵
↵
if(rank[u] < rank[v]) ↵
{↵
parent[u] = v;↵
rank[u]+=rank[v];↵
}↵
↵
else↵
{↵
parent[v] = u;↵
rank[v]+=rank[u]; ↵
}↵
}↵
↵
int main()↵
{↵
int N,m;↵
cin >> N >> m;↵
vector<node> edges;↵
↵
for(int i = 0;i<m;i++) ↵
{↵
int u, v, wt;↵
cin >> u >> v >> wt; ↵
edges.push_back(node(u, v, wt)); ↵
}↵
sort(edges.begin(), edges.end(), comp); ↵
↵
vector<int> parent(N);↵
for(int i = 0;i<N;i++) ↵
parent[i] = i;↵
↵
vector<int> rank(N, 1); ↵
↵
int cost = 0;↵
vector<pair<int,int>> mst; ↵
for(auto it : edges) ↵
{↵
if(find_set(it.v, parent) != find_set(it.u, parent)) ↵
{↵
cost += it.wt; ↵
mst.push_back({it.u, it.v}); ↵
union_set(it.u, it.v, parent, rank); ↵
}↵
}↵
cout << cost << endl;↵
for(auto it : mst) cout << it.first << " - " << it.second << endl; ↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:O ( E l o g V ) ↵
↵
Finding Strongly Connected Component(SCC)↵
-----------------------↵
↵
SCC of a directed graph is a subgraph such that ∃ a path b/w every pair of vertices of the subgraph. (In undirected graph,each component is a SCC.)↵
↵
Brute Force:↵
Find distance b/w every pair of vertices using floyd warshall algo.Take a node say 1 and push all nodes 'i' where dist[1][i]!=INF in a vector.For nodes pushed take all pairs say (i,j) and delete if the dist[i][j]==INF. Repeat this process.↵
TC:O(N^3).↵
↵
#### Kosaraju Algo↵
↵
**Intiution**↵
↵
If we consider a SCC as one node ,the graph formed will be DAG.↵
↵
If we reverse the direction of all edges of graph i.e. take transpose of graph ,the SCCs remain the same.↵
↵
For transpose of a DAG,if we visit nodes in topological order,for one DFS call from main(),only one node will be visited because there will be no outdegree. (source node has become sink node.)↵
↵
Steps:↵
↵
1. Find topological sorting of graph and store it in stack<int> topo.↵
↵
2. Find reverse of graph and store it in vector <vector <int> >transpose.↵
↵
3. Run DFS in topological order on reversed graph and store in vector <vector<int> > SCCs.↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
void dfs(int node, stack<int> &topo, vector<int> &vis, vector < vector<int> > &adj) ↵
{↵
vis[node] = 1; ↵
for(auto it: adj[node]) ↵
{↵
if(!vis[it]) ↵
{↵
dfs(it, topo, vis, adj); ↵
}↵
}↵
↵
topo.push(node); ↵
}↵
void revDfs(int node, vector<int> &vis, vector <vector <int> >transpose,vector<int> &component) ↵
{↵
vis[node] = 1; ↵
component.push_back(node);↵
for(auto it: transpose[node]) ↵
{↵
if(!vis[it]) ↵
revDfs(it, vis, transpose,component); ↵
}↵
}↵
vector <vector<int> > findSCCs(int n,vector <vector<int> > &adj)↵
{ ↵
↵
//Step-1:Find topo order↵
stack<int> topo;↵
vector<bool> vis(n, 0); ↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i]) dfs(i, topo, vis, adj); ↵
}↵
↵
//Step 2:Making transpose of graph↵
vector <vector<int> > transpose; ↵
↵
for(int i = 0;i<n;i++) ↵
{↵
vis[i] = 0; ↵
for(auto it: adj[i]) {↵
transpose[it].push_back(i); ↵
}↵
}↵
↵
//Step 3: DFS on transpose in topological order↵
vector <vector<int> > SCCs;↵
while(!st.empty()) ↵
{↵
int node = st.top();↵
st.pop(); ↵
if(!vis[node]) ↵
{↵
vector <int> component;↵
component.clear();↵
revDfs(node, vis, transpose,component);↵
SCCs.push_back(component);↵
}↵
}↵
↵
return SCCs;↵
↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:O(V+E) ↵
↵
Topics left:Bridges and articulation point --> very tough↵
----------------------↵
↵
↵
↵
↵
↵
Vertices,edges,undirected and directed graph,cyclic & acyclic graph,degree indegree & outdegree and weights.↵
In an undirected graph, the sum of degrees of all vertices is double the the no. of edges (We consider degree=indegree=outdegree in an undirected graph).↵
↵
Graph representation in C++↵
--------------------↵
Let us say there are n nodes and m edges. And adj[i][j] represents there is an edge from node i to j.↵
↵
There are two ways to represent a graph↵
↵
↵
#### 1. Adjacency matrix:↵
↵
↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
int n, m;↵
cin >> n >> m; ↵
int adj[n+1][n+1]; //1 based indexing ↵
for(int i = 0;i<m;i++) {↵
int u, v; ↵
cin >> u >> v;↵
adj[u][v] = 1; ↵
adj[v][u] = 1; //write this line only if the graph is undirected ↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity:**O(m)↵
**Space Complexity:**O(n*n)**↵
↵
↵
↵
#### 2. Adjacency List↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
int n,m;↵
cin >> n >> m; ↵
vector<vector<int> > adj(n+1); ↵
for(int i = 0;i<m;i++) {↵
int u, v; ↵
cin >> u >> v;↵
adj[u].push_back(v); ↵
adj[v].push_back(u); //undirected graph↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity:**O(m)↵
**Space Complexity:**O(n*n)↵
↵
If there are also weights in edges, we create the adjacency list as ' vector <vector < pair <int,int> > > ' where first value is node(v) and second value represents weight b/w the nodes(u and v).↵
↵
Since there can be multiple disconnected components in a graph, while graph traversal we have to call BFS/DFS from every unvisited node. To avoid repetition we store information if a node is visited or not by creating a boolean array where is_visited[i]==true represents node 'i' is visited.↵
↵
~~~~~↵
for(int i=1i<=n;i++)↵
{↵
if(!is_visited[i]) BFS(i);↵
}↵
~~~~~↵
↵
↵
BFS↵
---↵
Just after pushing a node in queue,make vis[node]=true;↵
Why we do vis[node]=true just after pushing the node in queue and not just after we pop it out of queue?↵
Because let say a node has two parents (possible in cyclic graph then it will be pushed in queue twice so we do vis[child]=1 on first encounter of the node so that on next encounter it is not pushed again.)↵
↵
<spoiler summary="code">↵
~~~~~↵
for(int i=0;i<n;i++)↵
{↵
if(!vis[i])↵
{↵
queue<int> q; ↵
q.push(i); ↵
vis[i] = 1; ↵
while(!q.empty()) ↵
{↵
int node = q.front();↵
q.pop();↵
cout<<node<<" "; ↵
for(auto child : adj[node]) ↵
{↵
if(!vis[child]) ↵
{↵
q.push(child);↵
vis[child] = 1; ↵
}↵
}↵
}↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)↵
↵
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for queue )↵
↵
DFS↵
---↵
why we do vis[node]=1 in startint or DFS fn and not do vis[child]=1 just like BFs?↵
↵
Because then vis[source_node] will never become 1.Otherwise it is same only.↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
void dfs(int node, vector<bool> &vis,vector <vector <int> > &adj) ↵
{↵
cout<<node<<" "; ↵
vis[node]=1; ↵
for(auto child : adj[node]) ↵
{↵
if(!vis[child]) ↵
{↵
dfs(child,vis,adj); ↵
}↵
}↵
}↵
↵
//Inside main()↵
for(int i = 1;i<=V;i++) ↵
{↵
if(!vis[i]) ↵
dfs(i, vis, adj); ↵
}↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)↵
↵
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for stack space )↵
↵
↵
↵
↵
Cycle Detection in Graphs↵
---↵
↵
#### Case 1: Cycle detection in undirected graph using dfs↵
↵
Since by definition, in an undirected graph, a cycle has at least three nodes,so we will need to store the parent of the node as well.↵
If a node adjacent to a node ( that is not its parent node ) is already visited, the component contains a cycle.↵
↵
<spoiler summary="code">↵
~~~~~↵
bool checkForCycle_DFS(int node, int parent, vector<int> &vis, vector <vector<int> > &adj) ↵
{↵
vis[node] = 1; ↵
for(auto child:adj[node])↵
{↵
if(vis[child]&&child!=parent) return true; ↵
if(!vis[child]) ↵
{↵
if(checkForCycle_DFS(child, node, vis, adj)) return true; ↵
}↵
↵
}↵
↵
return false; ↵
}↵
↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i])↵
{↵
if(checkForCycle_DFS(i, -1, vis, adj)) return true; ↵
}↵
↵
}↵
return false; ↵
~~~~~↵
</spoiler>↵
↵
#### Case 2:Cycle detection in the undirected graph using BFS↵
-------------↵
↵
<spoiler summary="code">↵
~~~~~↵
checkCycle_BFS(int node, int parent, vector<bool> &vis, vector <vector<int> > &adj)↵
{↵
vis[i]=1; ↵
queue<pair <int,int> > q; ↵
q.push({i,-1}); ↵
while(!q.empty()) ↵
{↵
int node = q.front().first;↵
int parent=q.front().second;↵
q.pop();↵
for(auto child : adj[node]) ↵
{↵
if(vis[child]&&child!=parent) return true;↵
if(!vis[child]) ↵
{↵
q.push({child,node});↵
vis[child] = 1; ↵
}↵
}↵
}↵
return false;↵
}↵
↵
//Inside main()↵
for(int i=0;i<n;i++)↵
{↵
if(!vis[i])↵
{↵
if(checkCycle_BFS(i,-1,vis,adj)) return true;↵
}↵
}↵
return false;↵
↵
~~~~~↵
</spoiler>↵
↵
#### Case 3:Cycle detection in the Directed graph using DFS-↵
↵
Think why color-coding of the graph is required in cycle detection in an undirected graph and why information about the parent of the node is not needed.↵
↵
<spoiler summary="code">↵
~~~~~↵
bool checkForCycle_DFS(int node, vector<int> &color, vector <vector<int> > &adj) ↵
{↵
color[node] = 1; ↵
for(auto child:adj[node])↵
{↵
if(color[child]==1) return true; ↵
if(!color[child]) ↵
{↵
if(checkForCycle_DFS(child,color, adj)) return true; ↵
}↵
↵
}↵
color[node]=2;↵
return false; ↵
}↵
↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i])↵
{↵
if(checkForCycle_DFS(i,vis, adj)) return true; ↵
}↵
↵
}↵
return false; ↵
~~~~~↵
</spoiler>↵
↵
#### Case 4:Cycle detection in the Directed graph using BFS↵
↵
Assume the directed graph to be acyclic i.e. DAG and find its topological order.If we can do topological sorting i.e. pushing all nodes in queue , the graph is acyclic,other wise it is cyclic.↵
↵
We increase our count by 1 (starting from 0) each time we push a node in queue. And if final value of count==no. of nodes in graph, the graph is a DAG.↵
↵
<spoiler summary="code">↵
~~~~~↵
//The given code is for one component graph. ↵
//You can find topological order for multiple component graph using vis array.↵
↵
bool isCyclic(int N, vector<int> adj[]) ↵
{↵
queue <int> q; ↵
vector <int> indegree(N, 0);↵
↵
for(int i = 0;i<N;i++) ↵
{↵
for(auto it: adj[i])↵
indegree[it]++; ↵
}↵
↵
for(int i = 0;i<N;i++) ↵
{↵
if(indegree[i] == 0) ↵
q.push(i); ↵
}↵
↵
int cnt = 0;↵
while(!q.empty()) ↵
{↵
int node = q.front(); ↵
q.pop();↵
cnt++;↵
for(auto it : adj[node]) ↵
{↵
indegree[it]--;↵
↵
if(indegree[it] == 0) ↵
q.push(it)↵
}; ↵
↵
} ↵
if(cnt == N) return false; ↵
return true;↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
Bipartite graph:↵
-------↵
↵
A graph will never be bipartite if it has a cycle with odd no. of nodes and if a graph has no cylces with odd no. of nodes, then it must be bipartite.↵
↵
#### Check whether a graph is bipartite or not using BFS↵
↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
bool bipartiteBFS(int src, vector <vector<int> > &adj, int color[]) ↵
{↵
color[src] = 1;↵
↵
queue<int> q;↵
q.push(src); ↵
↵
while(!q.empty()) ↵
{↵
int node = q.front(); ↵
q.pop();↵
↵
for(auto child : adj[node]) ↵
{↵
if(color[child] == color[node]) ↵
{↵
return false; ↵
}↵
else if(color[child] == -1) ↵
{↵
color[child] = 1 - color[node]; ↵
q.push(child); ↵
}↵
}↵
}↵
return true; ↵
}↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{ ↵
if(color[i] == -1) ↵
{↵
if(!bipartiteBFS(i, adj, color)) return false;↵
}↵
}↵
return true; ↵
~~~~~↵
</spoiler>↵
↵
↵
#### Check whether a graph is bipartite or not using DFS↵
↵
<spoiler summary="code">↵
~~~~~↵
bool bipartiteDfs(int node, vector <vector<int> > &adj, int color[]) ↵
{↵
for(auto child : adj[node]) ↵
{↵
↵
if(color[child] == color[node]) return false; ↵
else if(color[child] == -1) ↵
{↵
color[child] = 1 - color[node];↵
if(!bipartiteDfs(child, adj, color)) ↵
{↵
return false; ↵
}↵
}↵
}↵
return true; ↵
}↵
↵
//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(color[i] == -1) ↵
{↵
color[i] = 1;↵
if(bipartiteDfs(i, adj, color)==false) return false;↵
} ↵
}↵
return true; ↵
~~~~~↵
</spoiler>↵
↵
↵
Topological Sorting:↵
--------↵
↵
Only possible in DAG. It is a linear order of vertices such that for every directed edge u-->v, vertex u comes before v in that order. A DAG has at least one node with indegree=0.↵
↵
#### Topological sorting using BFS↵
↵
First, calculate indegree of all nodes and store it in vector.Then push all nodes with degree==0 in a queue.Take each node one by one out of queue and for all its child ,decrease their indegree by 1. After this if any child has indegree==0, push them in the queue.↵
↵
<spoiler summary="code">↵
~~~~~↵
//The given code is for one component graph. ↵
//You can find topological order for multiple component graph by calling this func for every unvisited node.↵
↵
vector<int> findTopo(int N,vector < vector <int> > &adj) ↵
{↵
vector<int> indegree(N, 0);↵
↵
for(int i = 0;i<N;i++)↵
for(auto it: adj[i]) ↵
indegree[it]++; ↵
↵
queue<int> q; ↵
for(int i = 0;i<N;i++) ↵
{↵
if(indegree[i] == 0) q.push(i); ↵
}↵
↵
vector<int> topo;↵
↵
while(!q.empty()) ↵
{↵
int node = q.front(); ↵
q.pop(); ↵
topo.push_back(node)↵
for(auto child : adj[node]) ↵
{↵
indegree[child]--;↵
↵
if(indegree[child] == 0)↵
q.push(child); ↵
↵
}↵
}↵
return topo;↵
}↵
~~~~~↵
</spoiler>↵
↵
#### Topological sorting using DFS↵
↵
Topological order is the order of nodes in decreasing order of finishing time i.e. the node that gets finished at last comes first in order.↵
↵
<spoiler summary="code">↵
~~~~~↵
//The given code is for one component graph. ↵
//You can find topological order for multiple component graph by calling this func for every unvisited node.↵
↵
void findTopoSort(int node, vector<int> &vis, stack<int> &st, vector<int> adj[])↵
{↵
vis[node] = 1; ↵
for(auto it : adj[node]) ↵
{↵
if(!vis[it]) ↵
findTopoSort(it, vis, st, adj); ↵
}↵
st.push(node); ↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
Shortest path algorithms:↵
------------------↵
↵
#### Shortest path of all nodes from a node in a unweighted/0-1 weighted graph.↵
↵
Use BFS for this because BFS visits nodes in a sequential manner. That is nodes at the same level are visited simultaneously.↵
Run BFS and equate dist[node] = 1+dist[parent].↵
↵
BFS can also be used to find shortest path in 0-1 weighted graph.Instead of using queue,use deque and if weight(node-->child)==0,push at front else at back of deque.↵
BFS can be used to make different binary string using this 0-1 trick. (e.g. in https://www.spoj.com/problems/ONEZERO)↵
↵
<spoiler summary="code">↵
~~~~~↵
void BFS(vector<int> adj[], int N, int src) ↵
{ ↵
int dist[N];↵
dist[src] = 0;↵
for(int i = 1;i<N;i++) dist[i] = INT_MAX; ↵
↵
queue<int> q;↵
q.push(src); ↵
↵
while(q.empty()==false) ↵
{ ↵
int node = q.front(); ↵
q.pop();↵
↵
for(auto it:adj[node])↵
{↵
//no use of vis array because if a dist[node] is relaxed from INT_MAX,↵
//it implies it is being visited first time.↵
if(dist[it]==INT_MAX)↵
{↵
dist[it]=dist[node]+1;↵
q.push(it);↵
}↵
} ↵
} ↵
for(int i = 0;i<N;i++) cout << dist[i] << " "; ↵
↵
} ↵
~~~~~↵
</spoiler>↵
↵
#### Shortest path of all nodes from a node in a weighted DAG ↵
↵
The weights can be -ve.↵
↵
Minimum sum to reach a node 'v' i.e. dist[v] is minimum of all (dist[u]+weight(u-->v)),where u is node from all its parents.↵
Similarly, dist[u] is calculated with the help of its parents.We can observe that ultimately we have to start calculating dist[] from source node and in topological order ,we have to visit the nodes↵
↵
We visit nodes in topological order and relax all its children. In this way, each node is relaxed by all its parents.↵
↵
<spoiler summary="code">↵
~~~~~↵
void shortestPath(int src, int N, vector<pair<int,int>> &adj) ↵
{ ↵
int vis[N] = {0};↵
stack<int> st; ↵
for (int i = 0; i < N; i++) ↵
if(!vis[i]) ↵
findTopoSort(i, vis, st, adj); ↵
↵
int dist[N]; ↵
for (int i = 0; i < N; i++) ↵
dist[i] = 1e9; ↵
dist[src] = 0; ↵
↵
while(!st.empty()) ↵
{ ↵
int node = st.top(); ↵
st.pop(); ↵
↵
if (dist[node] != INF) ↵
{↵
for(auto child : adj[node]) ↵
{↵
if(dist[node] + child.second < dist[child.first]) ↵
dist[child.first] = dist[node] + child.second; ↵
}↵
}↵
} ↵
↵
for (int i = 0; i < N; i++) ↵
(dist[i] == 1e9)? cout<< "INF ": cout << dist[i] << " "; ↵
} ↵
~~~~~↵
</spoiler>↵
↵
#### Shortest path in +ve weighted graph.↵
↵
Dijkstra's algorithm is basically an efficient version of breadth-first search on a different graph.↵
↵
Given a graph G with positive integer edge-weights, one could construct a new unweighted graph H, by replacing each weighted edge with a number of edges equivalent to its weight. So, for example, if you had an edge (u,v) with weight 10 in G, you'd replace this edge with a series of 10 edges between u and v.↵
↵
Since BFS visits nodes in increasing order of their level (distance from source node) i.e. at any point of time,if a node n1 level is smaller than node n2, minimum distance from n1 will be calculated earlier than n2. ↵
↵
From this, we get an intuition that at any point of time, calculate minimum distance of children of that node which is nearest to the source node. This is a kind of greedy approach because we are relaxing children of that node which is **locally**(at a point of time) nearest to the source.↵
↵
Since min_priority_queue always stores elements in increasing order,we will use it.We can also use set instead of it.↵
↵
<spoiler summary="code">↵
~~~~~↵
typedef pair<int, int> pi;↵
↵
vector <int> dijkstra(int n,vector<vector<pi>> &adj, int s)↵
{↵
priority_queue<pi, vector<pi>, greater<pi> > pq;↵
//min heap (weight,node)↵
↵
vector <int> dist(n);↵
for(int i=0; i<n; i++) dist[i]=1e9;↵
dist[s]=0;↵
↵
pq.push({dist[s], s});↵
↵
while (!pq.empty())↵
{↵
int u=pq.top().second;↵
pq.pop();↵
↵
for(auto p: adj[u])↵
{↵
int v=p.first;↵
int w=p.second;↵
if(dist[u] + w < dist[v]) ↵
{↵
dist[v] =dist[u] + w;↵
pq.push({dist[v], v});↵
}↵
}↵
↵
}↵
↵
return dist;↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
**Why Dijkstra doesn't work with -ve weights:**↵
↵
If all weights are non-negative, adding an edge can never make a path shorter but this is not valid if edge weight is -ve.Dry run a case to explain it further.↵
↵
Time Complexity:O((E+V)*logV) ↵
Space Complexity:O(V)↵
↵
#### Bellman Ford ↵
↵
Since the negative weighted cycle has sum — infinity, Bellman-Ford works in a directed graph iff the graph has no -ve weighted cycle and works in an undirected graph iff all weights are non -ve.↵
↵
Relax all edges n-1 times.Why exactly n-1 times.Since in each relaxation,in worst case,only one node will get relaxed and maximum distance of a node from source node is n-1.↵
Consider example 1-->2-->3-->4-->5. First 5 is relaxed,then 4 and so on till 2 ,n-1 times.↵
↵
Bellman Ford can also be used to detect -ve cycle in a graph.First relax all edges n-1 times.Then relax one more time.If any vertex is relaxed,then graph contains -ve cycle.↵
↵
<spoiler summary="code">↵
~~~~~↵
// dp[i] = shortest distance to node i↵
// dp[i] = INFINITY for all↵
↵
dp[s]= 0 ;↵
for ( int i= 1 ; i<=n -1 ; i++)↵
{↵
for ( auto e: edges)↵
{↵
int u=e.first;↵
int v=e.second.first;↵
int w=e.second.second;↵
↵
if (dp[u]+w <dp[v])↵
dp[v]=dp[u]+w;↵
↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
#### Floyd Warshall Algo:↵
↵
It gives the shortest distance b/w any two nodes.↵
↵
**Iterative DP code:**↵
↵
<spoiler summary="code">↵
~~~~~↵
void shortest_distance(vector<vector<int>>&weight)↵
{↵
int n=weight.size();↵
for(int k=0;k<n;k++)↵
{↵
for(int i=0;i<n;i++)↵
{↵
for(int j=0;j<n;j++)↵
{↵
if(i==j) dist[i][j]==0;↵
else↵
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);↵
}↵
}↵
}↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity:** :O(V*V*V)↵
↵
DSU↵
-----↵
↵
It is a data structure used to perform the union of disjoint sets efficiently.Each node in the set has parent.↵
↵
Representative node:Topmost node of a set whose parent is the node itself.↵
↵
**Naive Implementation:**↵
↵
<spoiler summary="code">↵
~~~~~↵
void make_set ( int n)↵
{↵
for ( int i= 0 ; i<n; i++)↵
{↵
par[i]=i;↵
}↵
}↵
↵
int find_set (int x)↵
{↵
if ( par[x] == x)↵
return x;↵
↵
return find_set(par[x]);↵
}↵
↵
int union_set(int a,int b)↵
{↵
int p1=find_set(a),p2=find_set(b);↵
//ensuring both nodes are not belonging to same set↵
if(p1!=p2)↵
par[p1]=p2;↵
}↵
~~~~~↵
</spoiler>↵
↵
Time complexity:O(n) for make_set and O(d) for find_set() and union_set() where d=maximum depth possible of a node.↵
↵
To reduce time complexity of find_set() and union_set(),we have to decrease depth.This can be possible if a parent has maximum children possible.↵
↵
We can do this by doing modification in find_set() and union_set():↵
↵
For finding representative node a node using find_set(), we will be traversing to its parent, grandfather and so on... . While traversing, we make a representative node,the parent of each node traversed.↵
↵
While merging two sets, we make the smaller-sized set child of the larger-sized set to ensure minimum depth. (visualize why so, by a diagram). To know the size of the set, we have to maintain an array ,where rnk[i] tells the size of the set treating 'i' as representative node.↵
↵
<spoiler summary="code">↵
~~~~~↵
void make_set (int n)↵
{↵
for (int i= 0 ; i<n; i++)↵
{↵
par[i] = i;↵
rnk[i] = 1 ;↵
}↵
}↵
↵
//While traversing ,we make representative node ,the parent of each node traversed.↵
int find_set ( int x)↵
{↵
if ( par[x] == x)↵
return x;↵
↵
par[x]=find_set(par[x]);↵
return par[x];↵
}↵
↵
void union_set ( int a, int b)↵
{↵
int p1 = find_set(a);↵
int p2 = find_set(b);↵
↵
if ( p1 == p2)↵
return ;↵
↵
if (rnk[p1] > rnk[p2])↵
{↵
par[p2]=p1;↵
rnk[p1] = rnk[p1] + rnk[p2];↵
}↵
↵
else↵
{↵
par[p1] = p2;↵
rnk[p2] = rnk[p1] + rnk[p2];↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
**Time complexity** :O(1)↵
↵
↵
↵
( Using path compression in find_set() alone reduces time complexity to O (log N)approximately. And time Complexity of find_set() and union_set(), when you use both path compression and union by rank: O( α(N) ) where α(N) = Inverse Ackermann Function which is approximately equal to O(1). )↵
↵
**3 Applications of DSU**↵
↵
1.Finding the number of components in a graph↵
↵
2. Finding MST↵
↵
3.Finding a cycle in undirected graph↵
↵
<spoiler summary="code">↵
~~~~~↵
make_set(n);↵
for( auto e: edges)↵
{↵
int u=e.first;↵
int v=e.second;↵
if ( find_set(u) == find_set(v) )↵
{↵
cout<<"Cycle found";↵
break;↵
}↵
union_set(u,v);↵
}↵
~~~~~↵
</spoiler>↵
↵
Minimum Spanning Tree:↵
---------------↵
↵
A spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. Thus it has n nodes and n-1 edges. A single graph can have many different spanning trees. ↵
↵
A minimum spanning tree (MST) for a weighted, connected, undirected graph is a spanning tree with sum of the weight of its all edges is less than or equal to the weight of every other spanning tree.↵
↵
####Prim's Algo to find MST:↵
↵
We will start from an empty mstSet and keep adding nodes till no. of nodes in mstSet=n. At any particular time,we will select that node from the children of all nodes already included in MST, whose edge formed will have minimum weight among all possible edges.↵
↵
This is a greedy approach because we are adding node in a sequence such that it gives least possible weight locally.↵
↵
**Implementation: **We will take a boolean vector mst to know which node is already included in mst.A int vector 'key',where key[node] stores minimum weight of among all possible edges made by node with its parent. Whenever a new node is inserted, for all children of it,we will↵
update key[child] if weight(node-->child)< key[child].We will insert child in priority queue only if the child has that node as minimum weighted edge among all its parents.We will also store parent[node] to print MST in future.↵
↵
↵
**Naive Implementation:** ↵
Finding minimum of key[node] values among all nodes will take O(n) time therefore, TC=O(n*n).↵
↵
**Optimal**↵
We will store {key[node],node} of all nodes in a priority queue so that node with minimum key[node] can be popped out in O(logn) time. ↵
↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
↵
vector <bool> mst(n,0);↵
vector <int> key(n,INT_MAX);↵
↵
//pii= pair<int,int>↵
priority_queue <pii,vector<pii>,greater <pii> > pq;↵
↵
//pq.top().first=key[node] (minimum) , pq.top().second=node↵
↵
key[0]=0;↵
pq.push({0,0});↵
parent[0]=-1;↵
↵
// Instead of counting till n-1,run the loop till all the nodes have been visited↵
// because here we simply take the minimal from the priority queue, so a lot of times a node might be taken twice↵
// hence its better to keep running till all the nodes have been taken. ↵
// try the following case: ↵
// 6 7 ↵
// 0 1 5 ↵
// 0 2 10 ↵
// 0 3 100 ↵
// 1 3 50 ↵
// 1 4 200↵
// 3 4 250↵
// 4 5 50 ↵
↵
while(!pq.empty())↵
{↵
int u=pq.top().second;↵
pq.pop();↵
↵
↵
mst[u]=true;↵
↵
//since 'u' is a newly inserted node,finding which child of will make minimum weighted edge↵
for(auto child:adj[u])↵
{↵
int v=child.first;↵
int w=child.second;↵
if(!mst[v]&&key[v]>w)↵
{↵
key[v]=w;↵
pq.push({key[v],v});↵
//if v is picked,we should know its parent↵
par[v]=u;↵
}↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
**Time Complexity: **O(nlogn)↵
↵
#### Kruskal's Algo to find MST:↵
↵
**Using Greedy+DSU :** ↵
Sort all edges in increasing order and keep including the edge only if the edge is not making a cycle.↵
This is greedy approach because we are trying to make globally minimum weight by selecting locally minimum weighted edge.To join to edges ,we use DSU operations,union_set and find_set.↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
struct node ↵
{↵
int u,v,w; ↵
node(int first, int second, int weight) ↵
{↵
u = first,v = second, wt = weight;↵
}↵
};↵
↵
bool comp(node a, node b) ↵
{↵
return a.wt < b.wt; ↵
}↵
↵
int find_set(int u, vector<int> &parent) ↵
{↵
if(u == parent[u]) return u; ↵
return parent[u] = find_set(parent[u], parent); ↵
}↵
↵
void union_set(int u, int v, vector<int> &parent, vector<int> &rank) ↵
{↵
u = find_set(u, parent);↵
v = find_set(v, parent);↵
↵
if(rank[u] < rank[v]) ↵
{↵
parent[u] = v;↵
rank[u]+=rank[v];↵
}↵
↵
else↵
{↵
parent[v] = u;↵
rank[v]+=rank[u]; ↵
}↵
}↵
↵
int main()↵
{↵
int N,m;↵
cin >> N >> m;↵
vector<node> edges;↵
↵
for(int i = 0;i<m;i++) ↵
{↵
int u, v, wt;↵
cin >> u >> v >> wt; ↵
edges.push_back(node(u, v, wt)); ↵
}↵
sort(edges.begin(), edges.end(), comp); ↵
↵
vector<int> parent(N);↵
for(int i = 0;i<N;i++) ↵
parent[i] = i;↵
↵
vector<int> rank(N, 1); ↵
↵
int cost = 0;↵
vector<pair<int,int>> mst; ↵
for(auto it : edges) ↵
{↵
if(find_set(it.v, parent) != find_set(it.u, parent)) ↵
{↵
cost += it.wt; ↵
mst.push_back({it.u, it.v}); ↵
union_set(it.u, it.v, parent, rank); ↵
}↵
}↵
cout << cost << endl;↵
for(auto it : mst) cout << it.first << " - " << it.second << endl; ↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:O ( E l o g V ) ↵
↵
Finding Strongly Connected Component(SCC)↵
-----------------------↵
↵
SCC of a directed graph is a subgraph such that ∃ a path b/w every pair of vertices of the subgraph. (In undirected graph,each component is a SCC.)↵
↵
Brute Force:↵
Find distance b/w every pair of vertices using floyd warshall algo.Take a node say 1 and push all nodes 'i' where dist[1][i]!=INF in a vector.For nodes pushed take all pairs say (i,j) and delete if the dist[i][j]==INF. Repeat this process.↵
TC:O(N^3).↵
↵
#### Kosaraju Algo↵
↵
**Intiution**↵
↵
If we consider a SCC as one node ,the graph formed will be DAG.↵
↵
If we reverse the direction of all edges of graph i.e. take transpose of graph ,the SCCs remain the same.↵
↵
For transpose of a DAG,if we visit nodes in topological order,for one DFS call from main(),only one node will be visited because there will be no outdegree. (source node has become sink node.)↵
↵
Steps:↵
↵
1. Find topological sorting of graph and store it in stack<int> topo.↵
↵
2. Find reverse of graph and store it in vector <vector <int> >transpose.↵
↵
3. Run DFS in topological order on reversed graph and store in vector <vector<int> > SCCs.↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
void dfs(int node, stack<int> &topo, vector<int> &vis, vector < vector<int> > &adj) ↵
{↵
vis[node] = 1; ↵
for(auto it: adj[node]) ↵
{↵
if(!vis[it]) ↵
{↵
dfs(it, topo, vis, adj); ↵
}↵
}↵
↵
topo.push(node); ↵
}↵
void revDfs(int node, vector<int> &vis, vector <vector <int> >transpose,vector<int> &component) ↵
{↵
vis[node] = 1; ↵
component.push_back(node);↵
for(auto it: transpose[node]) ↵
{↵
if(!vis[it]) ↵
revDfs(it, vis, transpose,component); ↵
}↵
}↵
vector <vector<int> > findSCCs(int n,vector <vector<int> > &adj)↵
{ ↵
↵
//Step-1:Find topo order↵
stack<int> topo;↵
vector<bool> vis(n, 0); ↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i]) dfs(i, topo, vis, adj); ↵
}↵
↵
//Step 2:Making transpose of graph↵
vector <vector<int> > transpose; ↵
↵
for(int i = 0;i<n;i++) ↵
{↵
vis[i] = 0; ↵
for(auto it: adj[i]) {↵
transpose[it].push_back(i); ↵
}↵
}↵
↵
//Step 3: DFS on transpose in topological order↵
vector <vector<int> > SCCs;↵
while(!st.empty()) ↵
{↵
int node = st.top();↵
st.pop(); ↵
if(!vis[node]) ↵
{↵
vector <int> component;↵
component.clear();↵
revDfs(node, vis, transpose,component);↵
SCCs.push_back(component);↵
}↵
}↵
↵
return SCCs;↵
↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
Time Complexity:O(V+E) ↵
↵
Topics left:Bridges and articulation point --> very tough↵
----------------------↵
↵
↵
↵
↵