Minimum Spanning Tree by kruskal

Algorithm Name: Kruskal
Algorithm Category:  Graph search algorithm

Source Code:
////////////////////////////////////////////// // Bismillahir Rahmanir Rahim // // Author : Shohan Ahmed Sijan // // Country : Bangladesh // // University : East West University // ///////////////////////////////////////// #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> using namespace std; #define N 1000 int i,node,tedge,leader[N]; struct st { int x,y,cost; }edge[N]; bool cmp(st a,st b) { return a.cost<b.cost; } int Leader(int X) { if(leader[X]==-1)return X; return leader[X]=Leader(leader[X]); } int main() { printf("How many node: "),scanf("%d",&node); printf("How many edge: "),scanf("%d",&tedge); printf("X Y Cost 1<=x,y<=n\n"); for(i=0;i<tedge;i++) scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].cost); sort(edge,edge+tedge,cmp); for(i=1;i<=node;i++) leader[i]=-1; int x1,y1,mincost=0,chose=0,cnt=0; printf("Edge for kruskal is:\n"); for(i=0;i<tedge && chose<node-1 ;i++) { x1=Leader(edge[i].x); y1=Leader(edge[i].y); if(x1!=y1) { printf("%3d %3d %3d\n",edge[i].x,edge[i].y,edge[i].cost); mincost+=edge[i].cost; leader[x1]=y1; chose++; } } for(i=1;i<=node;i++) if(leader[i]==-1) cnt++; if(cnt==1)printf("Lowest cost is %d\n",mincost); else printf("Not connected\n"); return 0; }

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

Output:
5 How many node: 5 How many edge: 7 X Y Cost 1<=x,y<=n 1 2 3 2 3 2 1 5 7 5 4 2 3 4 5 1 4 4 3 5 4 Edge for kruskal is: 2 3 2 5 4 2 1 2 3 1 4 4 Lowest cost is 11

Shortest path by Dijkstra

Algorithm Name: Dijkstra
Algorithm Category:  Graph search algorithm

Source Code:
////////////////////////////////////////////// // Bismillahir Rahmanir Rahim // // Author : Shohan Ahmed Sijan // // Country : Bangladesh // // University : East West University // ///////////////////////////////////////// #pragma warning(disable:4786) #include <cstdio> #include <queue> #include <iostream> #include <utility> using namespace std; #define Max 999999999 #define Size 1009 int node,edge,cost[Size],path[Size],start,dest,sc,i,j,c,source,destination; bool visit[Size]; pair <int,int>p,pp; queue< pair<int,int> >q[Size]; void Dijkstra(int s,int d) { cost[s]=0; priority_queue < pair<int,int> >pq; pq.push(pair<int,int>(-cost[s],s)); while(pq.empty()==false) { p=pq.top(); pq.pop(); sc=p.second; if(sc==d)break; visit[sc]=true; while(q[sc].empty()==false) { pp=q[sc].front(); q[sc].pop(); i=pp.first; if(visit[i]==false && cost[sc]+pp.second<cost[i]) { cost[i]=cost[sc]+pp.second; path[i]=sc; pq.push(pair<int,int>(-cost[i],i)); } } } } void getpath(int d) { if(path[d]!=-1) { getpath(path[d]); printf(" %d",d); } } int main() { scanf("%d %d %d %d",&node,&edge,&source,&destination); for(i=0;i<=node;i++) { cost[i]=Max; visit[i]=false; path[i]=-1; while(q[i].empty()==false) q[i].pop(); } for(i=0;i<edge;i++) { scanf("%d %d %d",&start,&dest,&c); q[start].push(pair<int,int>(dest,c)); q[dest].push(pair<int,int>(start,c)); } Dijkstra(source,destination); if(cost[destination]!=Max) { printf("Minimum cost is %d\n",cost[destination]); printf("Path is:%d",source); getpath(destination); printf("\n"); } else printf("Unreachable\n"); return 0; }

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

Output:
Minimum cost is 6 Path is:1 4 5

UVa Problem No:100 - The 3n + 1 problem

Source code of UVa Online Judge problem number: 100 - The 3n + 1 problem
Problem description: http://uva.onlinejudge.org/external/1/100.html

////////////////////////////////////////////// // Bismillahir Rahmanir Rahim // // Author : Shohan Ahmed Sijan // // Country : Bangladesh // // University : East West University // ///////////////////////////////////////// #include <stdio.h> int main() { long long i,j,max,temp,count,ii; while(scanf("%ld %ld",&ii,&j)!=EOF) { printf("%ld %ld",ii,j); if(ii>j) { temp = ii; ii = j; j = temp; } max = 0; for(i=ii;i<=j;i++) { temp = i; count = 1; if(temp>1) { do { if(temp%2==0) temp=temp/2; else temp=temp*3+1; count++; }while(temp!=1); } if(count>max) max = count; } printf(" %ld\n",max); } return 0; }