Mohammad Erfan Hossain's Blog

/* Solved by using Kruskal */ /* uva ID: shoaib05 . Accepted Time: 1.04 */ #include<iostream> #include<map> #include<string> #include<cstdio> #include<algorithm> using namespace std;  typedef struct list { int src; int dest; int wgt; }; list arr[79810]; int parent[410]; bool cmp(list x,list y) { return x.wgt<y.wgt; } int find(int x) { while(parent[x]!=x) x=parent[x]; return x; } int main() { int edge,node,i,w,u,v,expected_edge,up,vp,cost; string str,s; map<string,int> mymap; while(true) { cin>>node>>edge; if(edge==0 && node==0) break; mymap.clear(); for(i=1;i<=node;i++) { cin>>str; mymap[str]=i; } for(i=0;i<edge;i++) { cin>>str>>s>>w; arr[i].src=mymap[str]; arr[i].dest=mymap[s]; arr[i].wgt=w; } cin>>str; sort(arr,arr+edge,cmp); for(i=1;i<=node;i++) parent[i]=i; ...

/* kruskal code in C with using merge sort*/ #include<stdio.h> #define MAX 100 void merge(int *arr,int *order,int low,int mid,int high) { int i,j,k,temp[MAX],ord[MAX]; i=low; j=mid+1; k=low; while(i<=mid && j<=high) { if(arr[i]<arr[j]) { temp[k]=arr[i]; ord[k]=order[i]; i++; k++; } else { temp[k]=arr[j]; ord[k]=order[j]; j++; k++; } } if(i>mid) { while(j<=high) { temp[k]=arr[j]; ord[k]=order[j]; k++; j++; } } else { while(i<=mid) { temp[k]=arr[i]; ord[k]=order[i]; k++; i++; } } for(i=low;i<=high;i++) { arr[i]=temp[i]; order[i]=ord[i]; } } void divided(int *arr,int *ord,int low,int high) { int mid; if(low<high) { mid=(low+high)/2; divided(arr,ord,low,mid); divided(arr,ord,mid+1,high); merge(arr,ord,low,mid,high); } } void merge_sort(int *arr,int *ord,int low,int high) { for(...

/* Solved by using DFS- Timestamp &   DFS-Cycle */ /* uva Id: shoaib05 uva 247  -  Calling Circles Accepted Time: 0.043 */ #include<iostream> #include<string.h> #include<stack> #include<algorithm> #include<vector> #include<map> #include<string> using namespace std; typedef pair<int,int> pii; int table[30][30],trans[30][30],vis[30],f[30],d[30],counter,m,n; map<string,int> map1; map<int,string> map2; map<string,int>::iterator it; vector< pair<int,int> > vec; vector<string> output; void reset() { memset(table,0,sizeof(table)); memset(trans,0,sizeof(trans)); memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); map1.clear(); map2.clear(); } bool mysort(pair<int,int> p1,pair<int,int> p2) { if(p1.second>p2.second) return true; return false; } void dfs(int x) { int i; d[x]=counter; vis[x]=1; for(i=0;i<m;i++) { ...

/*Solution of uva 10004   Bicoloring Accepted Time: 0.000   */ #include<stdio.h> int table[210][210],color[210],queue[210]; int main() { int i,j,n,l,res,x,y,col,q,top; while(1) { scanf("%d",&n); if(n==0) break; for(i=0;i<n;i++) { table[i][0]=0; color[i]=0; } scanf("%d",&l); for(i=0;i<l;i++) { scanf("%d %d",&x,&y); table[x][0]++; table[x][table[x][0]]=y; table[y][0]++; table[y][table[y][0]]=x; } queue[0]=x; color[x]=1; q=0; top=1; res=1; while(q!=top) { x=queue[q]; q++; if(color[x]==1) col=2; else col=1; j=table[x][0]; for(i=1;i<=j;i++) { y=table[x][i]; if(color[y]==0) { color[y]=col; queue[top]=y; top++; } else if(color[y]!=col) { res=0; break; } } if(res==0) break; } if(res) printf("BICOLORABLE.\n...

/* Merge Sort */ #include<stdio.h> #define MAX 100 void merge(int *arr,int *order,int low,int mid,int high) { int i,j,k,temp[MAX],ord[MAX]; i=low; j=mid+1; k=low; while(i<=mid && j<=high) { if(arr[i]<arr[j]) { temp[k]=arr[i]; ord[k]=order[i]; i++; k++; } else { temp[k]=arr[j]; ord[k]=order[j]; j++; k++; } } if(i>mid) { while(j<=high) { temp[k]=arr[j]; ord[k]=order[j]; k++; j++; } } else { while(i<=mid) { temp[k]=arr[i]; ord[k]=order[i]; k++; i++; } } for(i=low;i<=high;i++) { arr[i]=temp[i]; order[i]=ord[i]; } } void divided(int *arr,int *ord,int low,int high) { int mid; if(low<high) { mid=(low+high)/2; divided(arr,ord,low,mid); divided(arr,ord,mid+1,high); merge(arr,ord,low,mid,high); } } void merge_sort(int *arr,int *ord,int low,int high) { for(int i=0;i<=high;i++) ...

/* Solved by using Dynamic Programming */ /* UVA 11258 -String Partition uva ID; shoaib05 Accepted Time: 0.003 */ #include<stdio.h> #include<string.h> #define MAX 2147483647 int main() { long long table[210],sum,val,mul; char ch[210]; int i,j,k,len,test; scanf("%d",&test); while(test--) { scanf("%s",ch); len=strlen(ch); table[0]=0; for(i=1;i<=len;i++) { table[i]=0; j=i; val=0; mul=1; while(j>=1) { j--; val=val+(ch[j]-48)*mul; if(val>MAX) break; sum=table[j]+val; table[i]=table[i]>sum?table[i]:sum; mul=mul*10; } } printf("%lld\n",table[len]); } return 0; }

/* Solved by using dynamic programming */ /* UVA problem ID: 11022 .  String Factoring uva id: shoaib05 Accepted Time: 0.025 */ #include<iostream> #include<string> using namespace std; int main() { freopen("in.txt","r",stdin); string str,templ,tempr,temp,tt; int i,j,k,x,len,table[85][85],min,l,mint,ltemp,index; bool flag; while(cin>>str) { if(str[0]=='*') break; len=str.size(); len--; for(i=0;i<=len;i++) table[i][i]=1; x=1; while(x<=len) { for(i=0,j=x;j<=len;i++,j++) { l=1; min=10000; flag=false; for(k=i;k<j;k++) { templ=str.substr(i,l); l++; if(table[i][k]==table[k+1][j]) { ltemp=templ.size(); for(index=i+ltemp;index<=j;index=index+ltemp) { flag=true; tt=str.substr(index,ltemp); { if(templ!=tt) { ...

/* Solved by using dynamic programming */ /* uva-10617 -Again Palindrome uva id: shoaib05 Accepted Time: 0.000 */ #include<stdio.h> #include<string.h> int main() { long long table[65][65]; char str[65]; int test,i,j,k,l,len,m; scanf("%d",&test); while(test--) { scanf("%s",str); len=strlen(str); len--; table[0][0]=1; for(i=1;i<=len;i++) { table[i][i]=1; table[i][i-1]=0; } k=1; while(k<=len) { for(i=0,j=k;j<=len;i++,j++) { table[i][j]=table[i][j-1]+1; for(m=i;m<j;m++) { if(str[m]==str[j]) table[i][j]=table[i][j]+table[m+1][j-1]+1; } } k++; } printf("%lld\n",table[0][len]); } return 0; }

/* Combinations of String */ #include<iostream> #include<string> #include<map> #include<vector> #include<set> #include<algorithm> using namespace std; typedef vector<string> vec_str; typedef map<int,vec_str> map_vec_str; bool mysort(string str1,string str2) { return str1.size()<str2.size(); } void calculation(string str,map_vec_str &res_map) { int i,j,length,len,vl,sl; string temp; char ch; length=str.size(); length--; for(i=0;i<=length;i++) { temp=""; temp.insert(0,1,str[i]); res_map[i].push_back(temp); } len=1; vec_str vec; while(len<=length) { ch=str[len]; for(i=0;i<len;i++) { vec=res_map[i]; vl=vec.size(); for(j=0;j<vl;j++) { temp=vec[j]; sl=temp.size(); temp.insert(sl,1,ch); res_map[i].push_back(temp); } } len++; } } void combination(string...