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↵


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

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

<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 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();↵
         ↵
        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 &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]=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↵
----------------------↵


  ↵

History

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