Wednesday, February 08, 2012

Web page Downloader in Java ( Basic URL connection) like facebook

/*
 * @(#)DownloadPage.java
 *
 *
 * @author Md. Saiful Islam
 * @Reg    :   2005331074
 * @version 1.00 2010/7/29
 */


import java.awt.*;
import java.io.*;
import java.net.InetAddress;
import java.net.*;
import java.util.*;
import java.math.*;
import java.lang.*;

public class DownloadPage
{      
    public DownloadPage() { }
   
    public static void main(String[] args)  throws  IOException
    {    
       
URL url;
InputStream is = null;
DataInputStream dis;
String Link,line,PageName;


Link = "http://www.facebook.com/";
FileOutputStream fileOutput;
PageName = "Download.html";



File file = new File(PageName);
file.createNewFile();
fileOutput = new FileOutputStream(file);



try
{
   url = new URL(Link);
 
   is = url.openStream();
   dis = new DataInputStream(new BufferedInputStream(is));

   while( ( line = dis.readLine() ) != null )
   {
       System.out.println(line);      
       fileOutput.write(line.getBytes());
   }
 
}

catch ( MalformedURLException waste )
{
    waste.printStackTrace();
}

catch ( IOException input )
{
    input.printStackTrace();
   }
 
finally
{

   try
   {
       is.close();
   }
    catch (IOException ioe)
    {
   
    }
} // End of finally
   
    } // End of main class
   
} // End of DownloadPage class

Topological Sort With Back Edge Or Cycle( UVA - 11686)

/***
    Topological Sort With Back Edge Or Cycle
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<vector>
#define mm 100000
using namespace std;


long ff,k,Node,Edge,a,b,x,aa[mm],flag[mm], tag;


vector< long >adjlist[mm];


void dfs_visit(long x)
{
    long i;
    flag[x] = 1;


    for(i = 0; i < adjlist[x].size(); i++)
    {
        ff=adjlist[x].at(i);
        if(flag[ff] == 0)
            dfs_visit(adjlist[x][i]);
        else if(flag[ff] == 1)
            tag = 1;
    }
    aa[k++] = x;
    flag[x] = 2;
}


int main()
{
    long i;
    while(scanf("%ld %ld",&Node,&Edge)==2 && (Node || Edge))
    {
        for(i=0;i<Node;i++)
        {
            flag[i] =0;
            adjlist[i].clear();
        }


        for(i=0;i<Edge;i++)
        {
            scanf("%ld %ld",&a,&b);
            adjlist[a-1].push_back(b-1);
        }
        tag = 0; k=0;
        for(i = 0;i < Node; i++)
        {
            if(flag[i] == 0)
            dfs_visit(i);
        }
        if(tag == 1)
        {
            printf("IMPOSSIBLE\n");
            continue;
        }
        else
        {
            for(i=k-1;i>=0;i--)
                printf("%ld\n",aa[i]+1);
        }
    }
    return 0;
}

Topological Sort (10305 - Ordering Tasks)

/***
Topological Sort
Author : Md.Saiful Islam
***/


#include<stdio.h>
#include<stdlib.h>


int Node,Edge,adjlist[102][102],a,b,start,i,x,front;
bool flag[110];
void dfs_visit(int x)
{
if( !flag[x])
{
flag[x] = 1;


for(i = 1;i <= adjlist[x][0];i++)
dfs_visit(adjlist[x][i]);


start++;
if(start != Node) printf("%d ",x);
else printf("%d",x);
}
}


int main()
{
while(scanf("%d%d",&Node,&Edge)==2 && (Node || Edge))
{
for(i=0;i<Edge;i++)
{
scanf("%d %d",&a,&b);
adjlist[b][++adjlist[b][0]] = a;
}
start = 0;


for(front = 1;front <= Node; front++)
dfs_visit(front);


for(i=1;i<=Node;i++)
adjlist[i][0] = flag[i] = 0;
printf("\n");
}
return 0;
}

Strongly Connected Component

/***
    Strongly Connected Component
    Author : Md.Saiful Islam
***/
#include<iostream>
#include<vector>
#define sz 10001
using namespace std;


vector<int>adj[sz];
int Node,Edge,u,v,array[sz],top,r;
bool Flag[sz];


void DFS(int u,bool s)
{
    if(Flag[u] == s) return;
    Flag[u]= s;
    for(int i=0;i<adj[u].size();i++)
        DFS(adj[u][i],s);
    if(s) array[top--]=u;
    return;
}


int main()
{
    int i,j,test,cnt,kase=1;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d",&Node,&Edge);
        for(i=1;i<=Edge;i++)
        {
            scanf("%d %d",&u,&v);
            adj[u].push_back(v);
        }
        top=Node; cnt=0;
        for(i=1;i<=Node;i++)
            if(!Flag[i])
                DFS(i,true);


        for(i=1;i<=Node;i++)
        {
            if( Flag[ array[i] ] )
            {
                DFS( array[i] , false );
                cnt++;
            }
            adj[ array[i] ].clear();
        }
        printf("Case %d: %d\n",kase++,cnt);
        for(i=0;i<=Node;i++)Flag[i] = false;
    }
    return 0;
}
/*
Input:
3
5 4
1 2
1 3
3 4
5 3


4 4
1 2
1 3
4 2
4 3


3 2
1 2
2 3
Output:
Case 1: 2
Case 2: 2
Case 3: 1
*/

Second Best MST (UVA 10462 - Is there any second way)

/***
    Second Best MST (UVA 10462 - Is there any second way)
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>
#define INF 99999999


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


int Set[203],Rank[203],store[203];
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 ( x->cost - y->cost );
}
int main()
{
int i,u_set,v_set,sum,set,test,ans,k,min,cnt,y,kase=1;


scanf("%d",&test);
while(test--)
{
scanf("%d %d",&Node,&Edge);
set  = 0;
for(i=0;i<=Node;i++)
{
make_set(i);
}
ans = -1;
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);


sum = k = 0;
for(i=0; i<Edge ;i++)
{
u_set=find_set(a[i].u);
v_set=find_set(a[i].v);
if( u_set!=v_set )
{
store[k++]=i;
sum += a[i].cost;
Union(u_set,v_set);
}
}


// second best MST start here
//if(k >= Node-1)ans = sum; // First MST Cost


min = INF;


for(y=0;y<k;y++)
{
sum = 0;
for(i=0;i<=Node;i++)
{
make_set(i);
}
for(i=cnt=0;i<Edge;i++)
{
if(store[y] != i)
{
u_set=find_set(a[i].u);
v_set=find_set(a[i].v);
if( u_set!=v_set )
{
cnt++;
sum += a[i].cost;
Union(u_set,v_set);
}
}
}
if(cnt >= Node-1 && sum < min) min = sum;
}
if(ans == -1)printf("Case #%d : No way\n",kase++);
else if(min == INF)printf("Case #%d : No second way\n",kase++);
else printf("Case #%d : %d\n",kase++,min);
}
return 0;
}
/*
Input:
4
5 4
1 2 5
3 2 5
4 2 5
5 4 5
5 3
1 2 5
3 2 5
5 4 5
5 5
1 2 5
3 2 5
4 2 5
5 4 5
4 5 6
1 0
Output:
Case #1 : No second way
Case #2 : No way
Case #3 : 21 // second best cost
Case #4 : No second way
*/

Minimum Spanning Tree (Prims Algorithm)

/***
    Minimum Spanning Tree (Prims Algorithm)
    Author : Md.Saiful Islam
***/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>


using namespace std;


#define SIZE 10000


struct pq
{
int cost,node;
bool operator<(const pq &b)const
{
return cost>b.cost;    // Min Priority Queue
}
};


int Prims(vector<pq>adj[],int source,int nodes)
{
priority_queue<pq>Q;
vector<int>color(nodes);
pq U,V;
int i,sum;


V.node=source;
sum=V.cost=0;
Q.push(V);
while(!Q.empty())
{
U=Q.top();
if(color[U.node]==0)
            sum+=U.cost;
color[U.node]=1;
Q.pop();
for(i=0;i<adj[U.node].size();i++)
{
if(color[ adj[U.node][i].node]==0)
{
V.node=adj[U.node][i].node;
V.cost=adj[U.node][i].cost;
Q.push(V);
}
}
}
return sum;
}


int main()
{
int nodes,edges,i,u,v,cost,source,val;
pq V;
vector<int>dist;
vector<pq>adj[SIZE];


while(scanf("%d %d",&nodes,&edges)==2)
{
for(i=0;i<nodes;i++)
{
adj[i].clear(); //clear adj vector
}
for(i=0;i<edges;i++)
{
scanf("%d %d %d",&u,&v,&cost);
V.cost=cost;
V.node=v;
adj[u].push_back(V);
V.node=u; //For Bidirectional Edges
adj[v].push_back(V);
}
val=Prims(adj,0,nodes);
printf("%d\n",val);
}


return 0;
}
/*
    Input:
    5 7
    0 1 5
    0 2 4
    1 2 2
    1 4 3
    2 4 1
    2 3 4
    3 4 3
    Output:
    10
*/

Minimum spanning tree Kurskal Using MAP + String

/***
    MST - Kurskal Using MAP + String
    UVA - 11710 Expensive Subway
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
int cnt,i,node,edge,sum,u,v,cost;
int rank[410],parent[410],array[79810][3];
char str[15];


map<string,int>flag;


int cmp(const void *a,const void *b)
{
   int *x = (int *) a;
   int *y = (int *) b;
   return *x - *y;
}


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;


else
{
parent[x]=y;


if(rank[x]==rank[y])    rank[y]=rank[y]+1;
    }
}


int main()
{
    while(scanf("%d %d",&node,&edge)==2 && (node || edge))
    {
        for(i=0;i<node;i++)
        {
            scanf("%s",str);
            flag[str]=i+1;
            parent[i]=i;
            rank[i]=0;
        }
        sum = cnt = 0;
        for(i=0;i<edge;i++)
        {
            scanf("%s",str);
            u = flag[str]-1;
            scanf("%s",str);
            v = flag[str]-1;
            scanf("%d",&cost);
            array[i][0]=cost;array[i][1] = u; array[i][2] = v;
        }
        qsort(array,edge,sizeof(array[0]),cmp);
        for(i=0;i<edge;i++)
        {
            u = array[i][1];
            v = array[i][2];
            cost = array[i][0];
            u = Find_Set(u);
            v = Find_Set(v);


            if(u!=v)
            {
                Link(u,v);
                cnt++;
                sum+=cost;


            }
        }
        scanf("%s",str);
        if(cnt!=node-1)
            printf("Impossible\n");
        else printf("%d\n",sum);
        flag.clear();
    }
    return 0;
}
/*
Input:
3 3
Picadilly
Victoria
Queensway
Picadilly Victoria 2
Queensway Victoria 10
Queensway Picadilly 20
Picadilly
4 2
Picadilly
Victoria
Queensway
Temple
Picadilly Victoria 2
Temple Queensway 100
Temple
Output:
12
Impossible
*/

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
*/

Tuesday, February 07, 2012

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.
*/