Strongly connected components and applications

Lets go over some basic terminology before getting into something serious.

Connected graph means where there is a path from any node to every node.

Strongly Connected Component (SCC) means the graph is divided into components or rather collection of nodes. Each component is a connected sub graph i.e. there is path from any node to every node within the sub graph.

In a DAG, the graph can be condensed to a smaller graph with less nodes by taking all connected component nodes into one node.

How to find connected components ?

1. Take any node and perform a DFS.
2. On the recursive way down, store the nodes in a stack.
3. Pop these nodes one by one and perform DFS from each.
4. The nodes that is reachable from each is the part of a new connected component and all the    reachable nodes are part of that CC.

This algorithm is called Kosaraju algorithm.

Proof is pretty simple. Refer to CLRS for that.

Applications:

If you are given a graph and asked to find the set of nodes which are reachable from all other nodes, how to approach?

First Approach : TLE

My first approach was to reverse the edges of the graph. Now I have to find the node which can "reach" all other nodes. The first thing that pops in mind is DFS! Apply DFS to every node and if a node can reach all in the transverse graph, it is reachable rom all in the original.
The time for a DFS is O(V+E). and this has to done on every node.
So TIme complexity is O(V^2 + EV). Meh thats too high. Lets think of another solution.

Second Approach : Better than before

A good observation in this would be, if a node (say X) can be reached by all nodes, then they can also reach all the nodes connected to that node X. That implies that all the nodes connected to X are the nodes we are trying to find. This means that if if divide the graph into Strongly Connected Components, One of these will be the component which can be reached by all. Another observation is that there will be no outgoing edge in this SCC. Why? See all the SCC's are connected to each other by atmost one edge. Now if suppose one edge of the "Reachable from all" SCC X is out going then the SCC Y that it connects to can't reach the X back and hence wont be reachable from Y.

So this has been established that SCC X has no out going edge. Now if a SCC has no outgoing edge and all incoming then only one such SCC can exist. (obviously)

Hence find all SCC's and then find the one with no outgoing edges, thats the collection of nodes reachable from all.

This question is gonna kill me : QUEEN #modifiedBFS #dijkstra Bonus Question : MLASERP

Took me 3 hours to do this one. But ahem! TLE TLE TLE I dont know what the hell is the matter with this. So I tried a similar problem with the same code and it was Accepted. Screw spoj.


So coming back to the topic!

Aakhir ye question kehna kya chahta hai?

There is a chess board with R rows and C columns. On the board there is one queen (obviously given the name of the problem) and obstacles. You are given the initial postion (S) and target position (F) of the queen.


Tell the minimum number of moves to reach the target.

Concept

I solved it using two methods but I'll tell the one using BFS.


If the queen is moving in the same direction, then no extra moves are needed to move it one more step but ifit changes its direction, one more move is needed. So with each move we have 3 parameters attached,



                          <Moves it now, x co-ordinate, y co-ordinate>


Now a simple method is to let the queen move in any one direction one by one stepwise. At each step, it can be counted as same move, so no new move is needed. So move the queen in all 8 directions one step wise and add each step to the queue as the current number of moves + 1.

Keep moving in a direction till



1. No obstacle

2. Within board

3. No visited cell with less moves than current


I'll explain the 3rd one. Suppose you reach a cell that you've already travelled to but with less moves, going on that cell again is redundant. So make an array of visited[][] to store the min moves to reach that cell.

Code

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define ppi pair<int,pair<int,int> >
#define ppp pair<int,pair<int,pair<int,int> > >
#define mp make_pair
#define INF 1e8
#define M(x,a) memset(x,a,sizeof(x))
using namespace std;

char grid [1005][1005];
int vis [1005][1005];
int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1},R, C,sx,sy,fx,fy;

int bfs(){
   
    queue<ppi> q;
    q.push(mp(0,mp(sx,sy)));
    vis[sx][sy]=0;
    while(!q.empty()){
        ppi temp=q.front();
        q.pop();
        int dist=temp.first,f=temp.second.first,s=temp.second.second;
        if(f==fx&&s==fy) return dist;
        if(dist>vis[f][s]||grid[f][s]=='X'||vis[f][s]==-1) continue;
        int j=1;
        REP(i,0,7){
            j=1;
            while(1){
            int xx=f+dx[i]*j,yy=s+dy[i]*j;
            if(xx>=0 &&xx<=R-1&&yy>=0&&yy<=C-1 && grid[xx][yy]!='X'){
                if(vis[xx][yy]>dist+1 ||vis[xx][yy]==-1) {
                    vis[xx][yy]=dist+1;
                    q.push(mp(dist+1,mp(xx,yy)));
                }
               
            }
            else break;
            j++;
            }
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    int t;
    scanf("%d",&t);
    while(t--){
        M(vis,-1);
        scanf("%d %d",&R,&C);
        REP(i,0,R-1) scanf("%s",grid[i]);
        REP(i,0,R-1) REP(j,0,C-1){
                if (grid[i][j]=='S')  
                    sx = i,sy=j;
                else if (grid[i][j]=='F')
                    fx = i,fy=j;
        }
       
        printf("%d\n", bfs());
    }
}

Similar problem : MLASERP

Then I solved a similar problem with a funny statement called MLASERP with cows who want to take using periscope and mirrors. Anywhoo, the code:

CODE :

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define ppi pair<int,pair<int,int> >
#define ppp pair<int,pair<int,pair<int,int> > >
#define mp make_pair
#define INF 1e8
#define M(x,a) memset(x,a,sizeof(x))
using namespace std;

char grid [1005][1005];
int vis [1005][1005];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},R, C,sx,sy,fx,fy;

int bfs(){
   
    queue<ppi> q;
    q.push(mp(0,mp(sx,sy)));
    vis[sx][sy]=0;
    while(!q.empty()){
        ppi temp=q.front();
        q.pop();
        int dist=temp.first,f=temp.second.first,s=temp.second.second;
    //    cout<<f<< " "<<s<<" "<<dist<<endl;
        if(f==fx&&s==fy) return dist;
        if(dist>vis[f][s]||grid[f][s]=='*'||vis[f][s]==-1) continue;
        int j=1;
        REP(i,0,3){
            j=1;
            while(1){
            int xx=f+dx[i]*j,yy=s+dy[i]*j;
            if(xx>=0 &&xx<=R-1&&yy>=0&&yy<=C-1 && grid[xx][yy]!='*'){
                if(vis[xx][yy]>dist+1 ||vis[xx][yy]==-1) {
                    vis[xx][yy]=dist+1;
                    q.push(mp(dist+1,mp(xx,yy)));
                }
               
            }
            else break;
            j++;
            }
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
   sx=-1;
   {
        M(vis,-1);
        scanf("%d %d",&R,&C);
        swap(R,C);
        REP(i,0,R-1) scanf("%s",grid[i]);
        REP(i,0,R-1) REP(j,0,C-1){
                if (grid[i][j]=='C'){  
                if(sx==-1)
                    sx = i,sy=j;
                else
                    fx = i,fy=j;
                }
        }
       
        printf("%d\n", bfs()-1);
    }
}

Bipartite graphs and a question on its application

BIPARTITE GRAPHS

If in a graph, we can divide the vertices into two disjoint set such that no two vertices in the same set is adjacent.

All acyclic graphs are bipartitie.

All the closed walks or cycles in it are of even length.

Complete Bipartite Graphs

Graphs with all the vertices in one set joining all other in the other set.

Crown Graph

Complete graph with horizontal edges removed.

Question Time!

http://www.spoj.com/problems/BUGLIFE/

Question kehna kya chahta hai?

There are male and female bugs in an experiment. As the experiment only allows non homo bugs, given which bug has sex with which bug, we have to tell if there is a mysterious homo among them.

Concept

We use the concept of 2-color coloring here. Its pretty simple. Initially all the nodes are white. Take a node. Mark it as red. Now mark all the adjacent nodes as black.
If you are on a red node and see that there is another red node adjacent to it...HOMO. Similarly with black.
If all the nodes are colored without any problem, no homos in the house.

How to do it?

Maintain an array of the color of nodes. and an array of visited nodes.
White==1
Red ==2
Black==3
Take a source node.
Apply dfs and color the nodes alternately and mark the visited nodes.
If two adjacent have same color, return -1 else return 0.

Code:

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int ans,grid[2005][2005],check[2005],color[2005];


int dfs(int v,int n){
    if(!color[v]) color[v]=1;

    for(int i=1;i<=n;i++){
        if(grid[v][i]){
            //cout<<v<<" "<<i<<" "<<color[v]<<" "<<color[i]<<endl;
            if(!color[i]) {color[i]= color[v]==1?2:1;if(dfs(i,n)) return 1;}
            else
            if(color[i]==color[v]) return 1;
        }
    }
    return 0;
}

int solve(int n){
    memset(check,0,sizeof(check));
    for(int i=1;i<=n;i++){
            if(!color[i]) if(dfs(i,n)) return 1;
    }
    return 0;
}


int main() {
    int t,tt=1;
    cin>>t;
   
    while(t--){
        memset(grid,0,sizeof(grid));
        memset(color,0,sizeof(color));
        int num,in,a,b;
        cin>>num>>in;
       
        while(in--){
            cin>>a>>b;
            grid[a][b]=1;
        }
       
        cout<<"Scenario #"<<tt++<<":\n";
        if(solve(num))
            cout<<"Suspicious bugs found!";
        else
            cout<<"No suspicious bugs found!";
        cout<<"\n";
    }
    return 0;
}
 

Diameter of any tree and applications

If there is a tree with N nodes. TO calculate the diameter,

1. Run bfs from any node and find the farthest node (say X) , this can be seen as a leaf node.

2. From X, run another bfs to find the farthest node form it. (Say Y).

3. The distance between X and Y is longest distance.

There can be many pair of nodes with the longest distance.

Application:

This can be used of find the best and worst nodes in the tree. Best node is the node, which if we make the root, the height of tree is minimised.

To find worst, find the pair of nodes with maximum distance. These are the worst nodes.

To find the best, find the nodes at half the distance of the maximum from the worst nodes.

To find the longest distance  

Code :

#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000
vector < int > g[MAXN + 1];
int maxWt[MAXN + 1];
bool check[MAXN + 1];
void bfs(int n)
{
    queue <pair<int, int> > q;
    q.push(make_pair(n, 0));
    while (!q.empty())
    {
        int root = q.front().first;
        int wt = q.front().second;
        check[root] = true;
        for(int i = 0; i<g[root].size(); i++)
        {
            if (!check[g[root][i]])
            {
                q.push(make_pair(g[root][i], wt + 1));
            }
        }
        maxWt[root] = wt;
        q.pop();
    }
}
int main()
{
    int n,a,b;
    cin>>n;
    vector<pair<int,int> > v[n+9];
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(1);
    int maxRoot = 0;
    for(int i = 1; i<= n; i++)
        maxRoot = maxWt[maxRoot] < maxWt[i] ? i : maxRoot;
    memset(maxWt, 0, sizeof(maxWt));
    memset(check, 0, sizeof(check));
    bfs(maxRoot);
    maxRoot = 0;
    for(int i = 1; i<= n; i++)
        maxRoot = max(maxRoot, maxWt[i]);
    cout<<maxRoot<<endl;
    return 0;
}

ESJAIL #modifiedDFS

One of the coolest question I have solved.

Question kehna kya chahta hai :

There is a prisoner, say Gabru. There is a prison with N chambers. In each chamber, there might be a locked door or an open door. And the key to that door will be in another chamber. For example the key to chamber 7 is in chamber 2. Needless to say, Gabru cannot pass through a locked door without first finding the key of that door. There are M corridors. Each corridor joins exactly two chambers.  Gabru has to reach the Nth chamber to escape.

Can Gabru escape?


Concept:

Do DFS on the first chamber. If you reach a locked door, MARK that locked door by maintaining an array to check if the door is locked or open. If you reach a key, check if the door that the key opens is marked or not. If the door is marked, that means now we can open that door and traverse all the corridors adjacent to it. So do another DFS from the door just unlocked.

Keep repeating this. Find key. Check if door marked. If marked, start DFS from there.

Why does this work? 

DFS is used to find the reachability of the nodes of the graph from a single source. So find the keys using DFS and unlock the corresponding door IF you can reach the door from the first chamber.

Code:

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define p(i) cout<<i<<endl;
#define M(x) memset(x,0,sizeof(x))
vector<int> *graph;
int n,k,m,a,b,*check;
int *key,*locked;
bool flag=false;

void dfs(int s) {
//    cout<<s<<" "<<locked[s]<<endl;
    check[s]=1; 
    if(locked[s]||flag) return;
   
    if(key[s] && check[key[s]]&&locked[key[s]]) { locked[key[s]]=0; dfs(key[s]);}
    if(key[s]) locked[key[s]]=0;
    if(s==n) {flag=true; return;}
    for(auto i:graph[s]){
        if(!check[i]) { dfs(i);}
    }
}
   

int main() {
    while(1){
        flag=false;
        cin>>n>>k>>m;
       
        if(n==-1) return 0;
        check=new int[n+1];
        locked=new int[n+1];
        key=new int[n+1];
        M(check);
        M(locked);
        M(key);
        graph = new vector<int>[n+1];
        REP(i,1,k){
            cin>>a>>b;
            if(b==n) continue;
            locked[b]=1;
            key[a]=b;
        }
       
        REP(i,1,m){
            cin>>a>>b;
        //    p(a);
        //    p(b);
            if(find(graph[b].begin(),graph[b].end(),a)==graph[b].end())
            graph[b].push_back(a);
            if(find(graph[a].begin(),graph[a].end(),b)==graph[a].end())
            graph[a].push_back(b);
        }
       
        dfs(1);
       
        if(flag)
        cout<<"Y\n";
        else
        cout<<"N\n";
    }
    return 0;
}

MELE3 #modified dijikstra

Question kehna kya chahta hai :

Elevator from node A to node B, takes 5 sec per floor and oscillates between A and B. We have to travel from floor 1 to last floor (N). At any floor there can be multiple stops of elevators.

Key points: 

So visualise it as a graph. At any node, we can ride any elevator, but we have to wait till the elevator comes and stops there. There can we multiple ways to reach the top. To find the quickest, we use dijikstra. Now I wont go into details of dijikstra but we maintain a priority queue that has minimum time node at the top.

The information we need to store in the queue with each element is: (time taken till now, floor on which we are currently)

If we have used an elevator, it will be redundant in using it again so we mark the elevator when we use it.

If we are on floor X, the quickest path can be through any one of the elevators that stop on it. So add all the elevators to queue.

We have to wait for the elevator to stop at the floor. For that we use the current time taken and the  time it takes for the elevator to oscillate.

Code:

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define ppi pair<int,pair<int,int> >
#define mp make_pair
#define INF 1e8
#define M(x) memset(x,0,sizeof(x))
using namespace std;

int graph[1005][1005];
int n,k,check[1005][1005],a,b;

void dij() {
    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(mp(0,1));
   
    while(!q.empty()){
        pii temp=q.top();
        q.pop();
        int time=temp.first,v=temp.second;
       
        if(v==n) {cout<<time<<endl; return;}
        REP(i,1,n){
            if(graph[v][i]&&!check[v][i]){
                check[v][i]=1;
                int vi=abs(v-i);
                if(graph[v][i]==1){
                    int mm=((10*(vi))-(time%((10*(vi)))))%((10*(vi)))+5*(vi);
        //            cout<<i<<" "<<time+mm<<endl;
                    q.push(mp(time+mm,i));
                }
                else{
                    int mm;
                    if(time>=5*(vi))
                    mm=((10*(vi))-((time-5*(vi))%((10*(vi)))))%((10*(vi)))+5*(vi);
                    else
                    mm=5*abs(v-i)-5*time;
        //            cout<<i<<" "<<time+mm<<endl;
                    q.push(mp(time+mm,i));
                }
            }
        }
    }
    cout<<-1<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    REP(i,0,k-1){
        cin>>a>>b;
        graph[a][b]=1;
        graph[b][a]=2;
    }
    dij();
}
   

Hello World

Just a new blog to look back on some questions and revise. I will be adding solutions to new questions that I encounter and find good or even average (For me everything question is hard). So yay! Here goes nothing..