Cities of Different Nations (Graph Theory):Breadth First Search Implementation and Combinatorics

Problem Discussion:

There are N cities numbered from 0 to N-1.Consider a country to be a set of many cities.For more clarity, all the cities in a country are somehow connected to each other.If A is a part of a country C, and B is connected to A, then B too lies in country C.  

The Prime Minister of Byteland wants to go to any two cities.The Prime Minister loves travelling and therefore, he wants to visit cities of different nations.Prime Minister, therefore, asked his Personal Assistant to calculate the number of ways of choosing two cities such that they are from different countries.

The Personal Assistant is not good in mathematics and therefore, has come to you for the answer.

Input:

The very first line contains an integer N, number of cities.The next line contains an integer P, total number of given connections.The ith line of the next P lines contains two integers Xi and Yi, meaning Xi and Yi cities are part of the same country.

Output:

Print the required answer, an integer, in a single line.

Constraints:

1<=N<=100000
0<=P<=min(N*(N+1)/2,100000)

Example:

Input:

4

2

0 1

2 3

Output:

4

Explaination:

Sets {0,1} and {2,3} form two countries.Two cities can be chosen in following ways:

city 0 and city 2

city 0 and city 3

city 1 and city 2

city 1 and city 3

Therefore, total number of ways of choosing two cities are 4.

Algorithm:

To find the required answer, we must know the number of cities in each nation.For calculating the number of cities in each nation, we can use Breadth First Search Algorithm.

Now, the if there are M nations and the total number of cities in ith nation be iCity then the required answer, Ans can be calculated as:

Solution:

/*

Problem Description:Cities of Different Nations

Submitted By

Arjun Mishra

*/

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

vector<LL> AdjList[100001];

queue<LL> Q;

LL count[100001],c=0,visited[100001]={},sum=0;

int main()

{

    LL i,N,L;

    cin>>N>>L;

    while(L--)

    {

        LL a,b;

        cin>>a>>b;

        AdjList[a].push_back(b);

        AdjList[b].push_back(a);

    } 

    //finding connected streaks

    for(i=0;i<N;i++)

    {

        LL ct=1;

        if(!visited[i])

        {

            visited[i]=1;

Q.push(i);

            while(!Q.empty())

            {

                LL temp,len;

                temp=Q.front();

                Q.pop();

                len=AdjList[temp].size();

                for(LL j=0;j<len;j++)

                {

                    if(!visited[AdjList[temp][j]])

                    {

                        ct++;

                        visited[AdjList[temp][j]]=1;

                    }   

                    Q.push(AdjList[temp][j]);

                }    

                AdjList[temp].clear();

        }

        count[c++]=ct;  

            sum+=ct;

        }    

    }

    LL ans=0;

    for(i=0;i<c;i++)

    {

        ans+=count[i]*(sum-count[i]);

    }    

    cout<<(ans/2)<<endl;

    return 0;

}

Even Forests (Graph Theory): Depth First Search Implementation

Problem Statement:

As we all know that Tree is basically a subset of Graph; a simple connected graph with no cycles.A tree with N nodes (numbered as 1,2,3,..,N) has N-1 edges.Forest is created when there exists two or more independent trees in a graph.Forest can be created by removing edges from a tree.

In this problem you will be given a tree with N nodes.You have to remove as many edges from the tree as possible to obtain a forest with condition that : Each connected component of the forest should contain even number of vertices.

Your task is to calculate the number of independent trees in that forest.

Consider that the tree is rooted at 1.

Input:

The first line of the input contains an integer N, where N is the number of nodes in a tree.Following N-1 lines contains two integers X and Y, where X is a child of Y.

Output:

Print the answer, a single integer.

Constraints:

1<=N<=100000
1<=X,Y<=N
                                                                                     
Example:

Input:

10
2 1
3 1
4 3                                          
5 2                                                                                      ORIGINAL TREE
6 1
7 2
8 6
9 8
10 8




Output:                                  
3                                                                              




                                                                                          DECOMPOSED TREE
Algorithm:

The problem can be easily solved using Depth First Search.For every node maintain the count information regarding total number of nodes for which the current node is their ancestor.

Solution:

/*
Problem Description:Even Forests

Submitted By
Arjun Mishra
*/

#include<iostream>
#include<vector>
#define MAX 100001
using namespace std;
vector<int> AdjList[MAX];
int nChild[MAX]={};
int dfs(int source)
{
int len=AdjList[source].size();
if(len==0)
{
nChild[source]=1;
return 1;
}
for(int i=0;i<len;i++)
{
nChild[source]+=(dfs(AdjList[source][i]));
}
nChild[source]+=1;
return nChild[source];
}
int main()
{
    int N,E;
    cin>>N;
    E=N-1;//number of edges in a tree
    while(E--)
    {
        int x,y;
        cin>>x>>y;//x is a child of y
        AdjList[y].push_back(x);
    }  
    //applying dfs
    int source=1,count=0;
    dfs(source);
    //counting ancestors with even number of nodes under them
    for(int i=1;i<=N;i++)
    if(nChild[i]%2==0)
    count++;
    //output, required answer
    cout<<count<<endl;
    return 0;

}    

Coding a Trie

Definition :

Trie is also called Digital Tree (sometimes Radix Tree or Prefix Tree).It is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

Solution:

/*
Trie Data Structure

Submitetd By
Arjun Mishra
*/

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define MAX_SIZE 26

//data structure for Trie<only for small letters>
struct Trie
{
int count;
int leaf;
struct Trie* next[MAX_SIZE];
Trie()//constructor
{
count=0;//initially not visited
leaf=0;//initially 0, means not a leaf
for(int i=0;i<MAX_SIZE;i++)
next[i]=NULL;//initially NULL
}
}*root,*ptr;

//function to insert into a trie
void insert(char str[6],int index,int len,struct Trie *R)
{
if(index==len)
{
return;
}
if(R->next[str[index]-'a']==NULL)
{
ptr=new Trie();
R->next[str[index]-'a']=ptr;
}
R->next[str[index]-'a']->count+=1;
if(index==(len-1))
R->next[str[index]-'a']->leaf=1;
insert(str,index+1,len,R->next[str[index]-'a']);
}

//function to traverse a trie
void getWords(struct Trie *R,char o[51],int index)
{

if(R==NULL)
return;
for(int i=0;i<MAX_SIZE;i++)
{
if(R->next[i]!=NULL)
{
//cout<<index<<endl;
o[index]=char(i+97);
if(R->next[i]->leaf==1)
{
for(int j=0;j<=index;j++)
cout<<o[j];
cout<<endl;
}
getWords(R->next[i],o,index+1);
}
}
}

//function to perform sleep operation
void sleep(int time_in_sec)
{
int start=clock();
while(clock()<=(start+time_in_sec*1000))
{
//empty loop
}
}

//main function, driver utility
int main()
{
ptr=new Trie();
root=ptr;
while(1)
{
int ch;
char str[51]={};
char o[51]={};
cout<<"Menu :\n\n";
cout<<"Enter 0 to exit\n";
cout<<"Enter 1 to insert into the dictionary\n";
cout<<"Enter 2 to traverse dictionary\n";
cout<<"\nEnter your choice :";
cin>>ch;
switch(ch)
{
case 0:
system("cls");
cout<<"Application By :\n\nArjun Mishra\nFinal Year Student\nMNNIT Allahabad";
return 0;
case 1:
system("cls");
cout<<"Insert word :";
scanf(" %s",str);
insert(str,0,strlen(str),root);
system("cls");
break;
case 2:
system("cls");
cout<<"All inserted words are\n\n";
getWords(root,o,0);
cout<<"\n\nPlease Wait...";
sleep(5);
system("cls");
break;
default:
system("cls");
cout<<"Wrong Choice\n";
sleep(2);
system("cls");
}
}
return 0;

}

Reverse Edges : Dijkstra's Algorithm Implementation

You have been given a directed graph consisting of N nodes and M edges.Vertices are numbered from 1 to N.The problem is to find the minimum number of edges that are needed to be reversed to reach the destination node from vertex 1.

Input:

The first line of the input contains two space separated integers N and M, denoting number of vertices and the number of edges respectively.The next ith line of the next M lines consists of two space separated integers Xi and Yi, denoting an edge directed from Xi to Yi.The last line of the input consists of an integer D, denoting the destination vertex.

Constraints:

1<=N,M<=100000

1<=Xi,Yi<=N

There can be multiple edges connecting the same pair of vertices.

There can be self loops too.

Output:

In a single line, print the minimum number of edges that we need to revert.If there is no way of reaching vertex D from vertex 1, print -1.

Example:

Input:
7 7
1 2 
3 2
3 4
7 4
6 2
5 6
7 5

7

Output:
2

Algorithm:




We will apply Dijkstra's Algorithm(for single source shortest path) to solve the given problem.Let the weight of the provided edges be 0 and for each given edge ,add a reverse edge of it having weight 1 unit.Now, apply Dijkstra's Algorithm for finding the minimum weighted path(path with minimum edges reversed) from vertex 1, or vertex 1 as a source.





Solution:


/*
Reverse Edges


submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define pp pair<int,int>
#define MAX 100001
#define INF 1000000000
//#define getchar_unlocked() getchar()
typedef long long LL;
using namespace std;
inline int read() //faster input for integer
{
 int n = 0;
 register char c = getchar_unlocked();//register is used due to its repeated use
 while (!('0' <= c && c <= '9'))
  {
    c = getchar_unlocked();
  }
  while ('0' <= c && c <= '9')
 {
   n = (n<<3) + (n<<1) +  c - '0';//equivalent to n = n*10 + c - 48;
   c = getchar_unlocked();
 }
 return n;
}
struct Prior
{
 int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second > p2.second;
    }
};
vector<pp> AdjList[MAX];
int dist[MAX],visited[MAX]={};
priority_queue<pp, vector<pp > , Prior > Queue;
//precomputation
void precompute()
{
 for(int i=0;i<MAX;i++)
 dist[i]=INF;//initially distance between vertex 1 and other vertices is infinity
}
int main()
{
 precompute();
 int N,M,D;
 N=read();
 M=read();
 while(M--)
 {
  int u,v;
  u=read();
  v=read();
        AdjList[u].push_back(pp(v,0));//given edge with weight 0
        AdjList[v].push_back(pp(u,1));//reverse edge with weight 1
 }
 D=read();
 //applying dijkstra
 int source=1;
    dist[source] = 0;
    Queue.push(pp(source,dist[source]));
    while(!Queue.empty())
    {
        int u,v,w;
 u = Queue.top().first;
        Queue.pop();
        int size = AdjList[u].size();
        for(int i = 0 ; i < size ; i++)
        {
            v = AdjList[u][i].first;
            w = AdjList[u][i].second;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                Queue.push(pp(v,dist[v]));
            }
        }
    AdjList[u].clear();
    }
    if(dist[D]==INF)//no path from 1 to D
    printf("-1\n");
    else
    printf("%d\n",dist[D]);
    return 0;
}