Category: Graph Algorithm

Tree construction from Inorder & Preorder [ Microsoft ]

Posted By: Asif NaeemPosted On:

Problem: Provided Inorder and PreOrder of a tree. Construct the tree and print it in PostOrder traversal. #include <stdio.h> #include <iostream> #include <string.h> #include<stdlib.h> #include <string> using namespace std; int preOrderIdx=0; struct Node{ int data; Node *left; Node *rit; }; int search(int in[],int in_stIndex,int in_endIndex,int data) { for(int i=in_stIndex;i<=in_endIndex;i++) { if(in[i]==data) return i; } }

Continue Reading “Tree construction from Inorder & Preorder [ Microsoft ]” →

10986

Posted By: Asif NaeemPosted On:

Single source shortest path algorithm and priority_queue used to solve the problem. #include <iostream> #include <queue> #include <cstdio> #include <vector> #define INF 1000000000 #define ll long long using namespace std; /* struct node{ int dest,weight; }; */ int n,m,src,dst; vector<pair<int,int> > vb[20005]; void dijkstra(vector<ll> distance) { int t_dist,t_node; int latency,v; pair<int,int> _intPair; priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int>

Continue Reading “10986” →

10336

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <vector> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <fstream> #include <string> #include <algorithm> #define INF 1000000000 #define ll long long using namespace std; int h,w; string arr[1010]; bool visit[1010][1010]; int stateCount[26]; struct stateInfo{ int count; int name; }; vector<stateInfo> vb; bool cmp(stateInfo a,stateInfo b) { if(a.count!=b.count) return a.count>b.count;

Continue Reading “10336” →

112

Posted By: Asif NaeemPosted On:

Tree Summing. #include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; int I; string str; int next_index; bool PATHFOUND; bool isEmpty(int a,int b) { if(a+1==b && str[a]=='(' && str[b]==')') return 1; return 0; } int findnum(int idx) { int numfoundAt=-1; int num=0; bool negative=false; for(int i=idx;i<str.size();i++) { if(str[i]!='(' && str[i]!=')') { numfoundAt =

Continue Reading “112” →

521

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <vector> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> using namespace std; int n,d,s; int BusStartAtStop[51]; int BusRunAtRoad[51]; int gr[31][31]; bool visit[51][51]; vector<int> vRoadstops[21]; vector<int> vBusRunAtRoad[21]; void init() { for(int i=0;i<51;i++) { BusStartAtStop[i]=0; BusRunAtRoad[i]=0; } for(int i=0;i<31;i++) for(int j=0;j<31;j++) gr[i][j]=0; for(int i=0;i<21;i++) { vRoadstops[i].clear(); vBusRunAtRoad[i].clear(); } } void

Continue Reading “521” →

794

Posted By: Asif NaeemPosted On:

This one took me a looong time to figure out the solution, i used dynamic programming approach to modify the bfs traversal. #include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <cstring> #include <fstream> #include <string> #include <map> #include <queue> #define INF 100000000 //#define ll long long #define PASS 2 #define NEED 1 #define NONEED

Continue Reading “794” →

710

Posted By: Asif NaeemPosted On:

This is quite an easy problem. But it took me long time to realize that to determine the number of total game segments is nothing but counting the direction changes to reach the destination. #include <iostream> #include <cstdio> #include <climits> #include <queue> #include <cstring> #include <string> using namespace std; int w,h; int SEGMENT; int gr[80][80];

Continue Reading “710” →

633

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; int stx,sty,edx,edy; int gr[405][405]; int dirx[8]={-2,-2,2,2,1,1,-1,-1}; int diry[8]={1,-1,1,-1,2,-2,2,-2}; int dx[4]={2,2,-2,-2}; int dy[4]={-2,2,2,-2}; int n; int bfs() { queue<int> q; int x,y; //int visit[405][405]; //memset(visit,0,sizeof(visit)); int moveTyp=0,move; int step=0,stepCount; q.push(stx);q.push(sty);q.push(moveTyp);q.push(step); if(gr[stx][sty]==1) return -1; else if(gr[edx][edy]==1) return -1; while(!q.empty()) { x = q.front();q.pop(); y

Continue Reading “633” →

627

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <sstream> #include <vector> #include <string> #include <cstring> #include <queue> using namespace std; vector<int> vb[305]; vector<int> par; bool bfs(int path[],int st,int ed) { int visit[400]; for(int i=0;i<400;i++) visit[i]=0; queue<int> q; q.push(st); visit[st]=1; int a,b; if(st==ed) return 1; while(!q.empty()) { a = q.front();q.pop(); if(a==ed) return 1; for(int i=0;i<vb[a].size();i++) { b = vb[a][i];

Continue Reading “627” →

599

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int parent[26]; int countNodes[26]; int getparent(int n) { if(parent[n]==n) return n; else return parent[n]=getparent(parent[n]); } void unite(int a,int b) { parent[getparent(a)]=getparent(b); } int main() { int t; string str; scanf("%d",&t); getchar(); while(t–) { str=""; for(int i=0;i<26;i++) { parent[i]=i; countNodes[i]=0; } while(getline(cin,str),str[0]!='*') { unite(str[1]-'A',str[3]-'A'); }

Continue Reading “599” →