Normal Kurskal algorithm (Cordinate Given)

/***
    Normal Kurskal (Cordinate Given)
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Node_num 10004

struct S
{
int u,v,cost;
};
S a[Node_num];

int Set[Node_num],Rank[Node_num];
int Node,Edge;
double x[10003],y[10003];

void make_set(int x)
{
Set[x] = x;
Rank[x] = 0;
}

int find_set(int x)
{
if(x != Set[x])
{
Set[x] = find_set(Set[x]);
}
return Set[x];
}

void Union(int x,int y)
{
if(Rank[x] > Rank[y])
{
Set[y] = x;
}
else
{
Set[x] = y;
if(Rank[x] == Rank[y])
{
Rank[y]++;
}
}
return;
}

int comp_fun(const void *m,const void *n)
{
S *x,*y;
x=(S*)m;
y=(S*)n;
return ( x->cost - y->cost );
}

int main()
{
int  test,n,k,i,j,u_set,v_set,flag;
double sum,t1,t2;

scanf("%d",&test);
while(test--)
{
flag = 1;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf %lf",&x[i],&y[i]);
k=0;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{

a[k].u=i+1,a[k].v=j+1;
t1=x[i]-x[j],t2=y[i]-y[j];
a[k].cost = t1*t1 + t2*t2;
k++;

}
}

qsort(a,k,sizeof(S),comp_fun);

for(i=0;i<=n;i++)
{
make_set(i);
}

sum = 0.0;
for(i=0; i<k ;i++)
{
u_set=find_set(a[i].u);
v_set=find_set(a[i].v);
if(u_set!=v_set)
{
sum += sqrt(a[i].cost);
Union(u_set,v_set);
flag = 0;
}
}
printf("%.2lf\n",sum);
if(test)
printf("\n");
}
return 0;
}
/*
Input:
1

3
1.0 1.0
2.0 2.0
2.0 4.0
Output:
3.41
*/

MST - Kurskal Algorithm

/***
    MST - Kurskal Algorithm
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>


struct S
{
int u,v,cost;
};
S a[10002];


int Set[1002],Rank[1002];
int Node,Edge;


void make_set(int x)
{
Set[x] = x;
Rank[x] = 0;
}
int find_set(int x)
{
if(x != Set[x])
{
Set[x] = find_set(Set[x]);
}
return Set[x];
}


void Union(int x,int y)
{
if(Rank[x] > Rank[y])
{
Set[y] = x;
}
else
{
Set[x] = y;
if(Rank[x] == Rank[y])
{
Rank[y]++;
}
}
return;
}


int comp_fun(const void *m,const void *n)
{
S *x,*y;
x=(S*)m;
y=(S*)n;
return ( y->cost - x->cost );
}
int main()
{
int i,taken,u_set,v_set,test,kase=1,max;


scanf("%d",&test);
while(test--)
{
scanf("%d %d",&Node,&Edge);


for(i=0;i<Edge;i++)
{
   scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].cost);
}
qsort(a,Edge,sizeof(S),comp_fun);


for(i=0;i<Node;i++)
{
make_set(i);
}


taken=1;max = 99999999;
for(i=0; taken<Node ;i++)
{
u_set=find_set(a[i].u);
v_set=find_set(a[i].v);
if( u_set!=v_set )
{
++taken;
if(a[i].cost <= max)
max = a[i].cost;
Union(u_set,v_set);
}
}
printf("Case #%d: %d\n",kase++,max);
}
return 0;
}
/*
Input:
2
2 3
0 1 10
0 1 20
0 0 30
4 5
0 1 1
3 1 2
1 2 3
2 3 4
0 2 5
Output:
Case #1: 20
Case #2: 3
*/

DisJoint Set Operation

/***
    DisJoint Set Operation
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>

int node,rank[50010],parent[50010],i,sum,edge,a,b,cnt=0,ans[50011],mx,test,temp;

int Find_Set(int x)
{
if(x != parent[x] )
parent[x]=Find_Set(parent[x]);
    return parent[x];
}
void Link(int x,int y)
{
if(rank[x]>rank[y])
{
        parent[y]=x;
        ans[x]+=ans[y];
}
else
{
parent[x]=y;
ans[y] += ans[x];
if(rank[x]==rank[y])
rank[y]=rank[y]+1;
}
}

int main()
{
int set;
    scanf("%d",&test);
while( test-- )
{
set = 0;
   scanf("%d %d",&node,&edge);

for(i=0;i<=50001;i++)parent[i]=i,rank[i]=0,ans[i]=0;
for(i=0;i<node;i++)
{
scanf("%d",&ans[i]);
}
cnt = 0;
for( i=0 ; i<edge ; i++ )
{
   scanf("%d %d",&a,&b);
            a = Find_Set(a);
   b = Find_Set(b);
if( a != b )
{
   Link(a,b);
}
}
for(i=0;i<node;i++)
{
if(parent[i] == i)
{
if(ans[i]!= 0)
{
set = 1;
break;
}

}

}
if(set)printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
return 0;
}
/*
Input:
2
5 3
100
-75
-25
-42
42
0 1
1 2
3 4
4 2
15
20
-10
-25
0 2
1 3
Sample Output
POSSIBLE
IMPOSSIBLE
*/

FloodFill With BFS using Knight moves

/***
    Knight moves Made by
    Author : Md.Saiful Islam
***/


#include<stdio.h>


int boa[10][10],que[65][2],flg,cost[65];
int x[]={-2,-2,-1,1,2,2,1,-1};
int y[]={-1,1,-2,-2,1,-1,2,2};


int Bfs(int c1,int r1,int c2,int r2)
{
if(c1==c2&&r1==r2)
return 0;
int h,t,i,c,r,tr,tc;
h=t=0;
que[h][0]=r1,que[h][1]=c1;
boa[r1][c1]=flg;
cost[h]=0;
h++;
while(t!=h)
{
r=que[t][0],c=que[t][1];
for(i=0;i<8;i++)
{
tr=r+x[i],tc=c+y[i];
if(tr>0&&tr<=8&&tc>0&&tc<=8&&boa[tr][tc]!=flg)
{
boa[tr][tc]=flg;
cost[h]=cost[t]+1;
if(tr==r2&&tc==c2)
return cost[h];
que[h][0]=tr,que[h][1]=tc;
h++;
}
}
t++;
}
return 0;
}


int main()
{
int r1,r2,n;
char c1,c2;
while(scanf("%c%d %c%d ",&c1,&r1,&c2,&r2) == 4)
{
flg++;
n=Bfs(c1-'a'+1,r1,c2-'a'+1,r2);
printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,r1,c2,r2,n);
}
return 0;
}
/*
Input:
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Output:
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
*/

FloodFill With BFS in 4 direction(657 - The die is cast)

#include<stdio.h>
#include<algorithm>
#define sz 11000

using namespace std;

struct st
{
int x, y;
}Q[sz*sz] ;

char mat[60][60];
int store[sz],res;

void BFS( st s )
{
st u ;
int front=0,rear=0;
int i, rr[4]={0,0,1,-1}, cc[4] = {1,-1,0,0};
mat[s.x][s.y] = '*' ;
Q[rear++] = s ;

while( front!=rear )
{
u = Q[front++] ;
for(i=0;i<4;i++)
{
if( mat[u.x+rr[i]][u.y+cc[i]] == 'X')   //??
{
mat[u.x+rr[i]][u.y+cc[i]]= '*';
Q[rear].x = u.x+rr[i] ;
Q[rear].y = u.y+cc[i] ;
rear++;
}
}
}
}
void BFS1( st s )
{
    printf("i = = %d j == %d\n",s.x,s.y);
st u ,v;
int front=0,rear=0;
int i, rr[4]={0,0,1,-1}, cc[4] = {1,-1,0,0};
mat[s.x][s.y] = '.';
    Q[rear++] = s ;

    while( front!=rear )
    {
        printf("front = %d %d\n",front,rear);
        u = Q[front++] ;

        for(i=0;i<4;i++)
        {
            if(mat[u.x+rr[i]][u.y+cc[i]] == 'X')
            {
                store[res]++;
                v.x=u.x+rr[i];
                v.y=u.y+cc[i];
                printf("v = %d %d\n",v.x,v.y);
                BFS(v);
            }
            else
            {
                printf("u = %d %d\n",u.x,u.y);
                mat[u.x+rr[i]][u.y+cc[i]]= '.';
                Q[rear].x = u.x+rr[i] ;
                Q[rear].y = u.y+cc[i] ;
                rear++;
            }
        }
    }
}

int main()
{
freopen("657.txt","r",stdin);
int r, c, i, j,kase=1;
char aa;
st u ;

while(scanf("%d %d ",&c,&r) == 2 && (r||c))
{
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%c",&aa);
mat[i][j] = aa;
}
scanf("%c",&aa);
}
res = 0 ;

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if( mat[i][j] != '.')
{
u.x = i ; u.y = j ;
printf("i == %d %d \n",i,j);
BFS1(u);
res++;
}
}
}

sort(store,store+res);

printf("Throw %d\n",kase++);
for(i=0;i<res;i++)
if(store[i]!=0)
{
printf("%d",store[i++]);
break;
}
for(;i<res;i++)
printf(" %d",store[i]);

printf("\n\n");
for(i=0;i<10100;i++)
            store[i] = 0;
}
return 0;
}

FloodFill With BFS in 8 direction

/***
    FloodFill With BFS
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#define sz 26


struct st
{
int x, y;
}Q[sz*sz] ;


int mat[sz][sz], line[sz] ;
int front, rear ;


void BFS( st s )
{
st u ;
int i, rr[8]={0, 0, -1,-1,-1, 1, 1, 1}, cc[8] = {1,-1, 0, -1, 1, -1, 0, 1};
mat[s.x][s.y] = 0 ;
Q[rear++] = s ;


while( front != rear )
{
u = Q[front++] ;
for(i=0;i<8;i++)
{
if( mat[u.x+rr[i]][u.y+cc[i]] == 1)
{
mat[u.x+rr[i]][u.y+cc[i]] = 0;
Q[rear].x = u.x+rr[i] ;
Q[rear].y = u.y+cc[i] ;
rear++;
}
}
}
}


int main()
{
int r, c, i, j, res,aa,kase=1;
st u ;


while( scanf(" %d",&r) == 1)
{
for(i=1;i<=r;i++)
{
for(j=1;j<=r;j++)
{
scanf(" %1d",&aa);
mat[i][j] = aa ;
}
}
res = 0 ;


for(i=1;i<=r;i++)
{
for(j=1;j<=r;j++)
{
if( mat[i][j] == 1)
{
res++;
front = rear = 0 ;
u.x = i ; u.y = j ;
BFS(u);
}
}
}
printf("Image number %d contains %d war eagles.\n",kase++,res);
}
return 0;
}
/*
Input:
6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000
Output:
Image number 1 contains 3 war eagles.
Image number 2 contains 6 war eagles.
*/

Directed path Floyd_Warshall algorithm

/***
    For Directed path Floyd_Warshall algorithm
Author : Md.Saiful Islam
***/
#include<stdio.h>
#define NIL 0
#define INF 99999


int cost[1008][1008],path[109][109];


void init(int n)
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
if(i == j)
cost[i][j] = NIL;
else cost[i][j] = INF;


path[i][j] = NIL; //to print path
}
}
return ;
}


void Floyd_Warshall(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j] > cost[i][k] + cost[k][j])
{
cost[i][j] = cost[i][k] + cost[k][j];
path[i][j] = path[k][j]; // to print path
}
}
}
}
return ;
}




void print_matrix_path(int n)
{
int i,j;


printf("\ndistance matrix:\n");


for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",cost[i][j]);
}
printf("\n");
}
printf("PATH matrix :\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",path[i][j]);
}
printf("\n");
}
}


void print_path(int s,int e)
{
if(path[s][e]==s)
{
printf("%d",path[s][e]);
return;
}
else if(path[s][e]==0)
{
printf("No path");
//pik=5;
}
else
{
print_path(s,path[s][e]);
printf(" %d",path[s][e]);
}
return;
}


int main()
{
int i,node,edge,s,e,t,a,b,c,j;
while(scanf(" %d%d",&node,&edge)==2 && (node || edge))
{
init(node);


for(i=1;i<=edge;i++)
{
scanf("%d%d%d",&a,&b,&c);
cost[a][b] = c;
}


//for print path && cycle


for(i=1;i<=node;i++)
{
for(j=1;j<=node;j++)
{
if(cost[i][j]!=INF  && i!=j)
{
path[i][j]=i;
}
}
}


Floyd_Warshall(node);


print_matrix_path(node);


scanf(" %d",&t);
while(t--)
{
scanf(" %d %d",&s,&e);


printf("saif\n");


print_path(s,e);


printf("%d\n",cost[s][e]);
}
}
return 0;
}