//  dfs

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int white=0,grey=1,black=2;
const int INF=100000,Nil=-1;
int timecnt=0;
struct node{
    int color,discovery,done,parent;
};
void dfs(vector<vector<int>> &graph,int nodes, vector<node> &Prop);
void dfs_visit(vector<vector<int>> &graph,int u, vector<node> &Prop);
int main(){
    int nodes,edges;
    cout<<"Enter the number nodes : ";
    cin>>nodes;
    cout<<"Enter the number of edges : ";
    cin>>edges ;
    vector<vector<int>> graph(nodes+1,vector<int>());
    vector<node> Prop(nodes+1,{white,INF,INF,-1});
    cout<<"Enter all the edges :-"<<endl;
    for(int i=0; i<edges; i++){
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
    }
    cout<<"Dfs order : ";
    dfs(graph,nodes,Prop);

    return 0;
}
void dfs(vector<vector<int>> &graph,int nodes, vector<node> &Prop){

    for(int i=0; i<=nodes ; i++){
        Prop[i].color=white ;
        Prop[i].parent=Nil;
    }
    timecnt=0;
    for(int i=1; i<=nodes ; i++){
        if(Prop[i].color==white){
            dfs_visit(graph,i,Prop);
        }
    }


}
void dfs_visit(vector<vector<int>> &graph,int u, vector<node> &Prop){
    cout<<" ->"<<u;
    timecnt++;
    Prop[u].discovery=timecnt;
    Prop[u].color=grey;
    for(int i=0,sz=graph[u].size(); i<sz ; i++){
        int n=graph[u][i];
        if(Prop[n].color==white){
            Prop[n].parent=u;
            dfs_visit(graph,n,Prop);
        }

    }
    Prop[u].color=black;
    timecnt++;
    Prop[u].done=timecnt;

}

//                      bfs

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int fx[]={1,-1,0,0};
int fy[]={0,0,1,-1};
int cell[201][201];
int d[201][201];
int vis[201][201];
int row,col;
void bfs(int sx, int sy)
{
    memset(vis,0,sizeof vis);
    vis[sx][sy] = 1;
    queue < pii > q;
    q.push(pii(sx,sy));
    while(!q.empty())
    {
        pii top = q.front();
        cout<<top.first<<" "<<top.second<<" ";
        q.pop();
        for(int k=0;k<4;k++)
        {
            int tx=top.first+fx[k];
            int ty=top.second+fy[k];
            if(tx>=0 && tx < row && ty>=0 && ty<col && cell[tx][ty] != -1 && vis[tx][ty] == 0)
            {
                vis[tx][ty] = 1;
                d[tx][ty] = d[top.first][top.second] + 1;
                q.push(pii(tx,ty));
            }
        }
    }
}
main()
{
    int n,e;
    while(cin>>n>>e)
    {
        memset(cell,-1, sizeof cell);
        row = n, col = n;
        for(int i=0;i<e;i++)
        {
            int x,y;
            cin>>x>>y;
            cell[x][y] = 1;
            if(i == e-1)
                bfs(x,y);
        }
    }
    return 0;
}

//          Floyd Warshall

#include<bits/stdc++.h>
#define V 4
#define INF 999999999
using namespace std;
void printSolution(int dist[][V]);
void floydWarshall (int graph[][V])
{

    int dist[V][V], i, j, k;

    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    for (k = 0; k < V; k++)
    {

        for (i = 0; i < V; i++)
        {

            for (j = 0; j < V; j++)
            {

                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    printSolution(dist);
}

void printSolution(int dist[][V])
{

    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == INF)
                cout<<"INF"<<"\t";
            else
                cout<<(dist[i][j])<<"\t";
        }
        printf("\n");
    }
}

int main()
{

    int graph[V][V] = { {0, 5, INF, 10},
                        {INF, 0, 3, INF},
                        {INF, INF, 0, 1},
                        {INF, INF, INF, 0}
                    };

    floydWarshall(graph);
    return 0;
}

//              Dijktra's

#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f

typedef pair<int, int> iPair;

class Graph
{
    int V;

    list< pair<int, int> > *adj;

public:
    Graph(int V);

    void addEdge(int u, int v, int w);

    void shortestPath(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair> [V];
}

void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}

void Graph::shortestPath(int src)
{

    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

    vector<int> dist(V, INF);

    pq.push(make_pair(0, src));
    dist[src] = 0;

    while (!pq.empty())
    {

        int u = pq.top().second;
        pq.pop();

        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;

            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

int main()
{
    int V = 9;
    Graph g(V);

    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);

    g.shortestPath(0);

    return 0;
}

//          Heap_sort

#include <iostream>

using namespace std;

void heapSort(int a[], int n, int h);
void buildMaxHeap(int a[], int n, int h);
void maxHeapify(int a[], int h, int i);
int left(int i);
int right(int i);

int main(){
    int a[20], n, h;
    cout << "How many numbers?: ";
    cin >> n;
    h = n;
    cout << "\nEnter numbers: ";
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    heapSort(a, n, h);
    cout << "\nOutput numbers in sorted order: ";
    for(int i = 1; i <= n; ++i)
        cout << " " << a[i];
    return 0;
}

void heapSort(int a[], int n, int h){
    buildMaxHeap(a, n, h);
    for(int i = n; i >= 2; --i){
        swap(a[1], a[i]);
        h--;
        maxHeapify(a, h, 1);
    }
}

void buildMaxHeap(int a[], int n, int h){
    h = n;
    for(int i = (n/2); i >= 1; --i)
        maxHeapify(a, h, i);
}

void maxHeapify(int a[], int h, int i){
    int l = left(i);
    int r = right(i);
    int largest;
    if(l <= h && a[l] > a[i])
        largest = l;
    else
        largest = i;
    if(r <= h && a[r] > a[largest])
        largest = r;
    if(largest != i){
        swap(a[i], a[largest]);
        maxHeapify(a, h, largest);
    }
}

int left(int i){
    return (2 * i);
}

int right(int i){
    return (2 * i + 1);
}

//          Insertion Sort

#include <bits/stdc++.h>
using namespace std;

void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

//          LCS

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

void lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];

for (int i=0; i<=m; i++)
{
    for (int j=0; j<=n; j++)
    {
    if (i == 0 || j == 0)
        L[i][j] = 0;
    else if (X[i-1] == Y[j-1])
        L[i][j] = L[i-1][j-1] + 1;
    else
        L[i][j] = max(L[i-1][j], L[i][j-1]);
    }
}


int index = L[m][n];


char lcs[index+1];
lcs[index] = '\0';

int i = m, j = n;
while (i > 0 && j > 0)
{
    if (X[i-1] == Y[j-1])
    {
        lcs[index-1] = X[i-1];
        i--; j--; index--;
    }

    else if (L[i-1][j] > L[i][j-1])
        i--;
    else
        j--;
}

cout << "LCS of " << X << " and " << Y << " is " << lcs;
}

int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
lcs(X, Y, m, n);
return 0;
}

//          Merge_Sort

#include<stdlib.h>
#include<stdio.h>

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2;

        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

//          Quick_Sort

#include<stdio.h>

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high- 1; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \t");
    printArray(arr, n);
    return 0;
}

//          Activity Selection

#include<bits/stdc++.h>
using namespace std;
bool custom_sort(pair<long long,long long> a, pair<long long,long long> b){
    return a.second<b.second;
}

int main(){
    long long int n;
    cout<<"Number of activity : ";
    cin>>n;
    cout<<"Enter all activities :-"<<endl;
    vector< pair<long long,long long> > activities ,ans;
    for(int i=0; i<n ; i++){
        long long st, sp;
        cin>>st>>sp;
        activities.push_back(make_pair(st,sp));
    }
    sort(activities.begin(),activities.end(),custom_sort);
    ans.push_back(make_pair(activities[0].first,activities[0].second));
    long long sp=activities[0].second;
    for(int i=1; i<n;i++){
        if(activities[i].first>=sp){
            ans.push_back(activities[i]);
            sp=activities[i].second;
        }
    }
    cout<<"All possible activities are :- "<<endl;

    for( auto i : ans ){
        cout<<i.first<<" "<<i.second<<endl;
    }

    return 0;
}

//              Binary Search

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r) {
        int m = l + (r - l) / 2;

        if (arr[m] == x)
            return m;

        if (arr[m] < x)
            l = m + 1;

        else
            r = m - 1;
    }

    return -1;
}

int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? printf("Element is not present"
                            " in array")
                : printf("Element is present at "
                            "index %d",
                            result);
    return 0;
}