Queue implement using two stack in python3

	Q.Implement queue using two Stack class Queue: def __init__(self):
	self.in_stack = []
	self.out_stack = []
	def enqueue(self, data):
	while self.out_stack:
	self.in_stack.append(self.out_stack.pop())
	self.in_stack.append(data)
	while self.in_stack:
	self.out_stack.append(self.in_stack.pop())
	def dequeue(self):
	if self.out_stack:
	self.out_stack.pop()
	def size(self):
	return len(self.out_stack)
	def frontData(self):
	if self.out_stack:
	return self.out_stack[-1]
	def __repr__(self):
	if self.out_stack:
	return '{}'.format(self.out_stack)
	def isEmpty(self):
	return not (bool(self.out_stack))
	if __name__ == '__main__':
	queue = Queue()
	print("Is the queue empty? ", queue.isEmpty())
	print("Adding 1 to 10 in queue element ")
	for i in range(1,11):
	queue.enqueue(i)
	print("Queue size : ", queue.size())
	print("Queue front data : ", queue.frontData())
	print("Remove queue front element ")
	queue.dequeue()
	print("Queue new front data : ", queue.frontData())
	print("Is the queue empty? ", queue.isEmpty())
	print("Printing the queue element : ")
	print(queue)
	queue.enqueue(44)
	queue.enqueue(99)
	print("Printing the new queue element : ")
	print(queue)
	print("Queue size : ", queue.size())
	print("Queue front data : ", queue.frontData())

Matt's Graph Book

--------------------------------------------------------------------------------------------------------
                                                #Python Solution
--------------------------------------------------------------------------------------------------------
import resource
import sys
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x10000001)

def dfs(u):
    visited[u] = 1
    for i in range(len(adj[u])):
        v = adj[u][i]
        if not visited[v]:
            dfs(v)
           
n = int(input())
m = int(input())
adj = []
visited = [0]*(n+1)
for _ in range(n+1): adj.append([])
for i in range(m):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)
d = int(input())
adj[d].clear()
dfs(1)
ans = 1
for i in range(n):
    if not visited[i]:
        ans = 0
        break
print("Connected" if ans else "Not Connected")
           

--------------------------------------------------------------------------------------------------------
                                                # C++ Solution
---------------------------------------------------------------------------------------------------------------------------------------------------

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

vector< int >adj[1000001];
vector< bool >visited(1000001,false);

void dfs(int u)
{
    visited[u] = true;
    for(int i = 0; i < adj[u].size() ; i++){
        int v = adj[u][i];
        if(visited[v] == false)
            dfs(v);
    }
}
int main()
{
    int n,m,x,y,d;
    cin >> n >> m;
    for(int i = 0; i < m ; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    cin >> d;
    adj[d].clear();
    dfs(1);
    bool ans  = true;
    for(int i = 0; i < n ; i++){
        if(visited[i] == false){
            ans = false;
            break;
        }
    }
    cout << ((ans)? "Connected" : "Not Connected" ) << endl;
    return 0;
}

Feasible relations

--------------------------------------------------------------------------------------------------------
                                                #Python Solution
--------------------------------------------------------------------------------------------------------

import resource
import sys
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x10000001)

def find(i):
    if(subset[i] != i):
        subset[i] = find(subset[i])
    return subset[i]

def UnionSet(x,y):
    xroot = find(x)
    yroot = find(y)
    subset[xroot] = yroot
   
t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    subset = [0]*(n+1)
    for i in range(n):
        subset[i] = i
   
    ans = 0
    for i in range(m):
        x,op,y = input().split(' ')
        x = int(x) - 1
        y = int(y) - 1
        if op == "=":
            UnionSet(x,y)
        elif find(x) == find(y):
            ans = 1
    print('YES' if not ans else 'NO')
           
 
--------------------------------------------------------------------------------------------------------
                                                # C++ Solution
--------------------------------------------------------------------------------------------------------

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

struct subset{
    int parent ,rank ;
};

int find(struct subset subsets[],int i){
    if(subsets[i].parent != i) subsets[i].parent = find(subsets,subsets[i].parent);
    return subsets[i].parent;
}

void UnioSet(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets,x);
    int yroot = find(subsets,y);

    if(subsets[xroot].rank < subsets[yroot].rank)subsets[xroot].parent = yroot;
    else if(subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot;
    else{
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int main()
{
    int t,n,m;
    cin >> t;
    while(t--){
            int x,y;
            string op ;
        cin >> n >> m;
        struct subset* subsets = (struct subset*) malloc((n+1)* sizeof(struct subset));
        for(int i = 0; i < n ; i++){
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }
        int ans = 0;
        for(int i = 0; i < m; i++){
            cin >> x >>  op >> y;
            if(op == "=")
                UnioSet(subsets,x,y);
            else if(find(subsets,x) == find(subsets,y)) ans = 1;
        }


      cout << ((ans == 1)? "NO\n" : "YES\n");
    }
    return 0;
}
 

Monk and Graph Problem

# Python Solution
 
import resource
import sys
sys.setrecursionlimit(0x100000)
#if you don't write this line you got runtime error ,coz python recursionlimit is soo poor , so you need upgrade recursionlimit
# Will segfault without this line.
#resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])

def find_component(u):
    global ans
    if component[u] != -1:
        return
       
    component[u] = 0
       
    for i in range(0,len(adj[u])):
        ans += 1
        find_component(adj[u][i])
           
           
n,m = map(int,input().split())
adj = []
component = [-1]*(100001)
for i in range(n+1): adj.append([])
for i in range(m):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)
res = 0
for i in range(1,n+1):
    ans = 0
    if (component[i] == -1):
        find_component(i)
        res = max(res,ans//2)
           
print(res)

#C++ Solution

#include< bits/stdc++.h >
using namespace std;
vector< int >adj[100001];
vector< int >component(100001,-1);
int n,ans = 0;
void find_component(int u)
{

    if (component[u] == 0) {
        return ;
    }
    component[u] = 0;

    for(int i = 0; i < adj[u].size() ; i++){
        ans++;
        find_component(adj[u][i]);
    }

}

int main()
{
    int m,x,y;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int components = 0,res = 0;
    for(int i = 1; i <= n; i++){
        ans = 0;
        if(component[i] == -1){
            find_component(i);
            // component++ if need how many component graph are present
        res = max(res,ans/2);
        }
    }
    cout << res << endl;
    return 0;
}
 
 

Happy Vertices (Python3)

def dfs(u):
    global ans
    for i in range(len(adj[u])):
        v = adj[u][i]
        if not visited[v]:
            visited[v] = len(adj[v])-1
            if visited[v] > visited[u]:
                ans += 1
            dfs(v)



n,m = map(int,input().split())
ans = 0
adj = []
for i in range(n+1): adj.append([])
for i in range(m):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)

visited = [0]*(n+1)
for i in range(1,n+1):
    if not visited[i]:
        visited[i] = len(adj[i])
        dfs(i)
print(ans)

Prison Break (Python3)

n = 0
def recursive(u,v):
    global ans
    if(u == n-1 and v == n-1):
        ans += 1
        return
    data[u][v] = 1

    if(u-1 >= 0 and data[u-1][v] == 0):
         recursive(u-1,v)
    if(u+1 < n and data[u+1][v] == 0):
        recursive(u+1,v)
    if(v-1 >= 0 and data[u][v-1] == 0):
         recursive(u,v-1)
    if(v+1 < n and data[u][v+1] == 0):
         recursive(u,v+1)
    data[u][v] = 0
   
    return
   
   
t = int(input())
for _ in range(t):
    n = int(input())
    data = []
    for i in range(n):
        data.append(list(map(int,input().split())))
    ans = 0
    recursive(0,0)
    print(ans)

Prison Break

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

int data[21][21];

int dfs(int u,int v,int n){
    int ans = 0;

    if( u == n and v == n) return 1;
    data[u][v] = 1;
    if(u - 1 >= 1 and data[u-1][v] == 0)
         ans += dfs(u-1,v,n);
    if(v - 1 >= 1 and data[u][v-1] == 0)
         ans += dfs(u,v-1,n);
    if(u+1 <= n and data[u+1][v] == 0)
         ans += dfs(u+1,v,n);
    if(v+1 <= n and data[u][v+1] == 0)
         ans += dfs(u,v+1,n);
    data[u][v] = 0;
 return ans ;
}
int main()
{
    freopen("in.txt","r",stdin);
    int n, t;
    cin >> t;
    while(t--){
    cin >> n;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
           cin >> data[i][j];

    if(data[1][1] == 1 and data[n][n] == 1) cout << 0 << endl;
    else cout << dfs(1,1,n) << endl;

    }
    return 0;
}

Happy Vertices

/*                             Name : Arif Khan
                                Date : 1/3/18
                                Problem Title: Happy Vertices
Problem Link : https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/happy-vertices/

*/

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

vector < int >adj[100001];
vector < int > visited(100001,0);
int ans = 0;

void dfs(int u){

    for(int i = 0; i < adj[u].size() ; i++){
        int v = adj[u][i];
        if(visited[v] == 0){
                visited[v] = adj[v].size() - 1;
            if(visited[v] > visited[u]) ans++;
            dfs(v);
        }
    }
}

int main()
{
    int n , m , x , y;
    cin >> n >> m;
    for(int i = 1; i <= m ; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i = 1; i <= n; i++){
        if(visited[i] == 0){
            visited[i] = adj[i].size();
            dfs(i);
        }
    }
    cout << ans << endl;
    return 0;
}

Bishu and his Girlfriend

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

vector< int > adj[1001];
vector< bool >visited(1000,false);
int dsit[1001];

void dfs(int s)
{
    memset(dsit,0,sizeof(dsit));

    stack < int > st;
    st.push(s);
    dsit[s] = 0;

    while(!st.empty()){
        int u = st.top();
        st.pop();
        for(int i = 0; i < adj[u].size() ; i++){
            int v = adj[u][i];

            if(v > dsit[u]+1){
                dsit[v] = dsit[u]+1;
                st.push(v);
            }
        }
    }
}

int main()
{
    int n,m;
    cin >> n;
    for(int i = 0; i < n-1; i++){
        int x,y;
        cin >> x >> y;
        // if undirected graph
        adj[x].push_back(y);
        adj[y].push_back(x); // if directed graph not needed this line
    }
    int res = INT_MAX,q,ans=0;
    cin >> q;
    int mal;
    dfs(1);
    for(int i = 0;i < q; i++){
        cin >> mal;
        if(dsit[mal] < res){
            res = dsit[mal];
            ans = mal;
        }else if(res == dsit[mal]){
            ans = min(ans,mal);
        }
      }
    cout << ans << endl;

    return 0;
}

Uri 2338 - Morse

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

int main()
{
    map < string , char > data;
    data["=.==="]        = 'a';
    data["===.=.=.="]    = 'b';
    data["===.=.===.="]    = 'c';
    data["===.=.="]        = 'd';
    data["="]        = 'e';
    data["=.=.===.="]    = 'f';
    data["===.===.="]        = 'g';
    data["=.=.=.="]    = 'h';
    data["=.="]        = 'i';
    data["=.===.===.==="]    = 'j';
    data["===.=.==="]        = 'k';
    data["=.===.=.="]    = 'l';
    data["===.==="]        = 'm';
    data["===.="]        = 'n';
    data["===.===.==="]        = 'o';
    data["=.===.===.="]    = 'p';
    data["===.===.=.==="]    = 'q';
    data["=.===.="]        = 'r';
    data["=.=.="]     = 's';
    data["==="]        = 't';
    data["=.=.==="]        = 'u';
    data["=.=.=.==="]    = 'v';
    data["=.===.==="]        = 'w';
    data["===.=.=.==="]    = 'x';
    data["===.=.===.==="]    = 'y';
    data["===.===.=.="]    = 'z';
    data["===.===.===.===.==="]    = '0';
    data["=.===.===.===.==="]    = '1';
    data["=.=.===.===.==="]    = '2';
    data["=.=.=.===.==="]    = '3';
    data["=.=.=.=.==="]    = '4';
    data["=.=.=.=.="]    = '5';
    data["===.=.=.=.="]    = '6';
    data["===.===.=.=.="]    = '7';
    data["===.===.===.=.="]    = '8';
    data["===.===.===.===.="]    = '9';
    data["=.===.=.===.=.==="]  = '.';
    data["===.===.=.=.===.==="]  = ',';
    data["=.=.===.===.=.="]  = '?';
    data["=.===.===.===.===.="]  = '\'';
    data["===.=.===.=.===.==="]  = '!';
    data["===.=.=.===.="]    = '/';
    data["===.=.===.===.="]    = '(';
    data["===.=.===.===.=.==="]  = ')';
    data["=.===.=.=.="]    = '&';
    data["===.===.===.=.=.="]  = ':';
    data["===.=.===.=.===.="]  = ';';
    data["===.=.=.=.==="]    = '=';
    data["=.===.=.===.="]    = '+';
    data["===.=.=.=.=.==="]  = '-';
    data["=.=.===.===.=.==="]  = '_';
    data["=.===.=.=.===.="]  = '"';
    data["=.===.===.=.===.="]  = '@';
    string line;
    int n,tc = 0;
    cin  >>  n;
    getline(cin,line);
    while(n--){
        if(tc != 0) cout << endl;
        int dot = 0;
        getline(cin,line);
        string text;
        for(int i = 0;  i < line.size() ; i++ ){
            if(line[i] == '.') dot++;
            else{
                if(dot == 3) text += " ";
                else if(dot == 7)  text += "  ";
                else if(dot == 1) text += '.';
                text +=  line[i];
                dot = 0;
            }
        }
        line  = text;
        stringstream word;
        word << line;

        while(word >> line){
            cout << data[line];

            if(word.good()){
                char ch = word.get();
                     ch = word.peek();
                 if(ch == ' ' ) cout << " " ;
            }
        }
        cout << endl;
    }

    return 0;
}

Donald Knuth Biography :

Donald Knuth Biography :

Born: 10 January 1938 in Milwaukee, Wisconsin, USA

 

Uri 1667 - HTML

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);cin.tie(NULL);

string s;

char ch;

while(scanf("%c",&ch)!=EOF){

s+=ch;

}

stringstream str1(s);

vector < string > variable;

string take;

while (str1 >> take)

variable.push_back(take);

int len = 0;

string sd;

for(int i = 0; i < variable.size() ; i++){

bool b = true;

sd = variable[i];

string st = (i != 0)? variable[i - 1] : sd ;

if(len+sd.size() > 80 and sd != "< br >" and sd[sd.size()-1] != '.') {

cout << endl, len = 0;

}else if(len+sd.size()+1 > 80 and sd != "< br >" and sd[sd.size()-1] == '.'){

cout << endl, len = 0;

}

if(st[st.size()-1] == '.' and len > 75 and sd != "< br >"){

cout << endl, len = 0;

}

if(variable[i] == "< br >"){

cout << endl;

len = 0,b=false;

}

else if(variable[i] == "< hr >")

if(len!=0) cout << endl << "--------------------------------------------------------------------------------\n", len = 0,b = false;

else cout << "--------------------------------------------------------------------------------\n",len = 0,b=false;

else (i == 0 or len == 0)? cout << variable[i] : cout << " " << variable[i] ;

if(b) len += sd.size()+1;

}

if(sd != "< br >")cout << endl;

return 0;

}

Uri 2248 - Internship

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

struct ans{
    int a = 0;
    int b = 0;
}rec[1511];

bool cmp(const ans &x, const ans &y){
    return x.b > y.b;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
     int n ,m,k,l,ca = 0;

     while(cin >> k and k){
          for(int i = 0; i < k ;i++){
            cin >> rec[i].a >> rec[i].b;
          }
          stable_sort(rec,rec+k,cmp);

     cout << "Turma " << ++ca << endl;

       bool b = true;

     for( int i = 1 ;i < k ; i++){
            if(b) cout << rec[i-1].a << " " ;

            if(rec[i].b != rec[i-1].b and b) {
                cout << endl ;
                    b = false;
             }
             rec[i-1].a = 0, rec[i-1].b = 0;
      }

      if(b) cout << rec[k-1].a << " " << endl;
      rec[k].a = 0, rec[k].b = 0;

      cout << endl ;
     }
    return 0;
}

Uri 1652 - Deli Deli

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

int main(){
    string s,s1;
    int n,k;
    cin >> n >> k;
    map < string , string > ans;
    while(n--){
        cin >> s >> s1;
        ans.insert(pair < string , string > (s,s1));
            }
            while(k--){
                cin >> s;
                s1 = s;
                if(ans.count(s) != 0)
                    cout << ans.find(s)->second << endl;
                else{
                    if(s[s.size()-1] == 'y' and (s[s.size()-2] != 'a' and s[s.size()-2] != 'e' and s[s.size()-2] != 'i' and s[s.size()-2] != 'o' and  s[s.size()-2] != 'u'))
                        s[s.size()-1] = 'i',s +="es";
                    else if(s[s.size()-1] == 'o' or (s[s.size()-1] == 's') or (s[s.size()-2] == 'c' and (s[s.size()-1] == 'h')) or (s[s.size()-2] == 's' and s[s.size()-1] == 'h') or (s[s.size()-1] == 'x'))
                        s += "es";
                    else
                        s += "s";
                    cout << s << endl;
                    ans.insert(pair(s1,s));
                }
            }
    return 0;
}

Uri 1832 - EBCDIC

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

int octal_to_decimal(int oc){
  int d = 0, i = 0, rem;
    while (oc != 0)
    {
        rem = oc % 10;
        oc /= 10;
        d += rem * pow(8, i);
        ++i;
    }
    return d;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    long n,k = 0;
    string s;
        int Tableebc2Asc[256] =
    {
            32,  32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 91, 46, 60, 40, 43, 33,
            38, 32, 32, 32, 32, 32, 32, 32,
            32, 32, 93, 36, 42, 41, 59, 94,
            45, 47, 32, 32, 32, 32, 32, 32,
            32, 32,124, 44, 37, 95, 62, 63,
            32, 32, 32, 32, 32, 32,238,160,
            161, 96, 58, 35, 64, 39, 61, 34,
            230, 97, 98, 99,100,101,102,103,
            104,105,164,165,228,163,229,168,
            169,106,107,108,109,110,111,112,
            113,114,170,171,172,173,174,175,
            239,126,115,116,117,118,119,120,
            121,122,224,225,226,227,166,162,
            236,235,167,232,237,233,231,234,
            158,128,129,150,132,133,148,131,
            123, 65, 66, 67, 68, 69, 70, 71,
            72, 73,149,136,137,138,139,140,
            125, 74, 75, 76, 77, 78, 79, 80,
            81, 82,141,142,143,159,144,145,
            92, 32, 83, 84, 85, 86, 87, 88,
            89, 90,146,147,134,130,156,155,
            48, 49, 50, 51, 52, 53, 54, 55,
            56, 57,135,152,157,153,151, 32
    };
    while(getline(cin,s)){
            vector < string > ans;
            stringstream stl(s);
            string take;
            while (stl >> take)
            ans.push_back(take);

            for(int i = 0 ; i < ans.size() ; i++){
            stringstream str2(ans[i]);
            int p = 0;
            str2 >> p;
            unsigned char d = octal_to_decimal(p);
            (i != ans.size()-1)?printf("%c",Tableebc2Asc[d]) : printf("%c\n",Tableebc2Asc[d]);
            }
    }
    return 0;
}

Uri 2252 - Discovering Password

#include <bits/stdc++.h>
using namespace std;
typedef long double LD;

template
struct less_first {
    typedef pair < T1, T2 > type;
    bool operator ()(type const& a, type const& b) const {
        return a.first > b.first;
    }
};

int main()
{
    //freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n,c = 0;
    while(cin >> n){
        map < LD, int > ans;
        LD a;
        for(int i = 0; i < 10 ;i++) {
                cin >> a;
         while(ans.count(a) != 0){
            a -= (LD)1e-15;
         }
        ans.insert(pair < LD,int > (a,i));
        }
     vector < pair < LD, int > > ans1(ans.begin(), ans.end());
     sort(ans1.begin(), ans1.end(), less_first < LD, int > ());
     vector > :: iterator it = ans1.begin();

     int i = 0;
     cout << "Caso " << ++c << ": ";
     for( vector < pair < LD, int > > :: iterator it = ans1.begin() ; it != ans1.end() ;it++,i++){
        if(i == n) break;
        cout << it->second ;
     }
        cout << endl;
    }
    return 0;
}

Uri 1945 - Simulator

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

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    string s;
    map < string , int > ans;
    int res;
    while(getline(cin,s)){

    stringstream str1(s);
    vector < string > variable;
    string take;
    while (str1 >> take)
    variable.push_back(take);

        int l = variable.size();

        if(l == 3){
        string ds = variable[2];

        if(isdigit(ds[0])){
            stringstream str2(variable[2]);
            int p = 0;
            str2 >> p;
            ans.insert(pair < string , int > (variable[0],p));
            res = p;
        }else{
            ans.insert(pair < string , int > (variable[0],ans.find(variable[2])->second));
            res = ans.find(variable[2])->second;
        }
    }else{
       ans.insert(pair < string , int > (variable[0],(ans.find(variable[2])->second) + ans.find(variable[4])->second));
       res = ans.find(variable[2])->second + ans.find(variable[4])->second ;
      }
    }
    cout << res << endl;
    return 0;
}

Uri 2344 - Notas da Prova

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

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;
    cin >> n;
    cout << ((n == 0)? 'E' : (n < 36)? 'D' : (n < 61)? 'C' : (n < 86)? 'B' : 'A') << endl;
    return 0;
}