Revise Complete Graphs For Interview | C++
Difference between en34 and en35, changed 0 character(s)
--------------------↵

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↵

<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[v][u] = 1; //write this line only if the graph is undirected ↵
}↵
~~~~~↵
</spoiler>↵

**Time Complexity:**O(m)****↵
Space Complexity:**O(n*n)**↵

<spoiler summary="code">↵
~~~~~↵
int n,m;↵
cin >> n >> m;  ↵
for(int i = 0;i<m;i++) {↵
int u, v; ↵
cin >> u >> v;↵
}↵
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↵
---↵

<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<<" "; ↵
{↵
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↵
---↵

<spoiler summary="code">↵
~~~~~↵
void dfs(int node, vector<bool> &vis,vector <vector <int> > &adj) ↵
{↵
cout<<node<<" "; ↵
vis[node]=1; ↵
{↵
if(!vis[child]) ↵
{↵
}↵
}↵
}↵

//Inside main()↵
for(int i = 1;i<=V;i++) ↵
{↵
if(!vis[i]) ↵
}↵
~~~~~↵
</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; ↵
{↵
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();↵
{↵
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])↵
{↵
}↵
}↵
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; ↵
{↵
if(color[child]==1) return true; ↵
if(!color[child]) ↵
{↵
}↵
↵
}↵
color[node]=2;↵
return false; ↵
}↵

//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(!vis[i])↵
{↵
}↵
↵
}↵
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++) ↵
{↵
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++;↵
{↵
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();↵
↵
{↵
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) ↵
{↵
}↵
}↵
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[]) ↵
{↵
{↵
↵
if(color[child] == color[node]) return false; ↵
else if(color[child] == -1) ↵
{↵
color[child] = 1 - color[node];↵
{↵
return false; ↵
}↵
}↵
}↵
return true; ↵
}↵

//Inside main()↵
for(int i = 0;i<n;i++) ↵
{↵
if(color[i] == -1) ↵
{↵
color[i] = 1;↵
} ↵
}↵
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++)↵
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)↵
{↵
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;     ↵
{↵
if(!vis[it]) ↵
}↵
st.push(node); ↵
}↵
~~~~~↵
</spoiler>↵

Shortest path algorithms:↵
------------------↵

#### Shortest path of all nodes from a node in a uni-weighted undirected 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();↵
↵
{↵
//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]) ↵
↵
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) ↵
{↵
{↵
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();↵

{↵
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 &mdash; 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.↵

<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.↵

ShortestPath(i,j,k)=the shortest path from i to j using the vertices from 1 to k in the graph.↵

ShortestPath(i,j,0)=weight(i,j) //Base Case↵

ShortestPath(i,j,k)=min(ShortestPath(i,j,k−1),ShortestPath(i,k,k−1)+ShortestPath(k,j,k−1)).↵

**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). )↵

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;↵
pq.push({0,0});↵
parent=-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↵
{↵
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[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; ↵
{↵
if(!vis[it]) ↵
{↵
}↵
}↵
↵
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; ↵
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↵
----------------------↵

↵

#### History

Revisions Rev. Lang. By When Δ Comment
en35 harshiscoding 2022-05-29 14:19:28 0 (published)
en34 harshiscoding 2021-12-12 18:30:08 47
en33 harshiscoding 2021-12-12 18:28:58 241
en32 harshiscoding 2021-12-12 12:44:47 1008
en31 harshiscoding 2021-12-11 22:11:56 57
en30 harshiscoding 2021-12-11 22:08:01 190
en29 harshiscoding 2021-12-11 21:17:12 334
en28 harshiscoding 2021-12-11 18:51:41 18 Tiny change: 'ouble the vertices (We con' -> 'ouble the the no. of edges (We con'
en27 harshiscoding 2021-10-02 02:07:28 38
en26 harshiscoding 2021-10-02 02:06:13 776
en25 harshiscoding 2021-10-02 01:31:17 88
en24 harshiscoding 2021-10-02 01:29:02 21237
en23 harshiscoding 2021-10-02 01:28:45 11261 Reverted to en21
en22 harshiscoding 2021-10-02 00:57:40 11261 Reverted to en16
en21 harshiscoding 2021-10-02 00:57:20 2367 Reverted to en9
en20 harshiscoding 2021-10-02 00:56:37 23786 Reverted to en8
en19 harshiscoding 2021-10-01 22:03:18 5435
en18 harshiscoding 2021-09-30 13:26:59 2377
en17 harshiscoding 2021-09-30 01:11:18 910
en16 harshiscoding 2021-09-30 00:51:45 2037
en15 harshiscoding 2021-09-29 23:26:56 2409
en14 harshiscoding 2021-09-29 22:37:35 1295
en13 harshiscoding 2021-09-29 22:18:17 2063
en12 harshiscoding 2021-09-29 21:42:26 112
en11 harshiscoding 2021-09-29 21:40:43 802
en10 harshiscoding 2021-09-29 21:29:57 2367
en9 harshiscoding 2021-09-29 20:39:11 2367 Tiny change: '\n==================\n' -> '\n========\n'
en8 harshiscoding 2021-09-27 19:09:00 231
en7 harshiscoding 2021-09-27 18:46:00 1502
en6 harshiscoding 2021-09-27 17:14:14 138
en5 harshiscoding 2021-09-27 17:10:22 257
en4 harshiscoding 2021-09-27 17:08:58 228
en3 harshiscoding 2021-09-27 17:06:13 703
en2 harshiscoding 2021-09-27 16:42:44 15 Tiny change: 'ologies:\n\nbhbm\n==================' -> 'ologies:\n==================\n\nhvh'
en1 harshiscoding 2021-09-27 16:41:52 90 Initial revision (saved to drafts)