Saiful's World

Write a program that reverses alternate elements in a given linked list input: a->b->c->d->e, output should be b->a->d->c->e

2013-01-23T02:17:00.000+06:00

Node reverseAlterante ( Node head) {
if ( head == null || head.next == null )
return head;
Node r = reverseAlternate(head.next.next);
Node t = head.next ;
t.next = head;
head.next = r;
return t ;
}

Printing all possible subsets using BitMask

2013-01-21T00:20:00.001+06:00

#include<stdio.h>

void PrintAllSubset(int n)
{
int mask,pos,i,j,noOfSubSet = 1<<n; // subset size 2^n subsets
for(i=1;i<noOfSubSet;i++)
{
for(j=0;j<n;j++)
if((i&(1<<j)) > 0)
printf("%d ",j+1);
printf("\n");
}
}
int main()
{
int n;
while(scanf("%d",&n) == 1)
{
PrintAllSubset(n);
}
return 0;
}

Write a function to print all subsets of a certain size of the numbers from 1 to n

2012-12-11T21:06:00.000+06:00

#include <iostream>
#include <stdio.h>

using namespace std;
const int MAX = 1000;
int a[MAX];
bool b[MAX];
void f1(int n, int k, int indexn, int indexk){
int i, j;
for(i = indexn; i <= n - k + indexk; i++){
if(!b[i]) {
b[i] = true;
a[indexk] = i;
if(indexk == k) {
for(j = 1; j <= k; j++) {
printf("%d ", a[j]);
}
printf("\n");
} else {
f1(n, k, indexn + 1, indexk + 1);
}
b[i] = false;
}
}
}
void f(int n, int k) {
int i;
for(i = 1; i <= n; ++i) {
a[i] = i;
b[i] = false;
}
f1(n, k, 1, 1);
}

int main()
{
int n,k;
while(scanf("%d %d",&n,&k) == 2)
{
f(n,k);
}

return 0;
}

Unable to establish a secure connection to iTunes/iPhone

2012-11-23T10:24:00.000+06:00

"Could not establish a secure connection to the device."

Here's what you have to do. You need a backup of your old Mac prior to upgrading, or prior to wiping and reinstalling.

You need to open Console on your new mac, and see the error message when you plug your phone into itunes and get that error, this will show up in your console:

8/13/12 1:21:04.537 PM iTunes[491]: AMDeviceValidatePairing (thread 0x11c313000): Could not load pairing record /var/db/lockdown//<device id>.plist

Then you need to go to your time machine backup and navigate to that same folder, and find the missing file. Copy that file back to your new machine into the /var/db/lockdown and you will magically be able to access your device again.

Make Xcode(4.x) faster

2012-11-13T23:52:00.000+06:00

How to make xcode faster

Buying more memory.
Disable indexing if you are building out huge projects in Xcode. This can halve Xcode’s memory consumption.
Running Xcode in 32 bit. This is not an option for everyone, because it will exceed 4 GB in larger projects.
Reduce the number of build processes (again).
Restarting Xcode often (It doesn’t do a very good job cleaning up after itself).
Use clang as your compiler. Clang instances in general use less memory than Apple’s GCC 4.2.
Offload dependent targets which do not change often. Example: You will not need to rebuild third party libraries daily in most cases.

Indexing in xcode

Xcode 4 has an entirely new mechanism for indexing files in a workspace. An index is created for the entire workspace, so references across projects are resolved.

The indexer now uses the LLVM compiler 2.0 to parse source files. This results in improved performance and higher accuracy; most importantly, the interpretation of symbols for indexing more closely matches the interpretation of syntax at compile time.

The index is stored in the Index subdirectory of the workspace’s unique directory in ~/Library/Developer/Xcode/DerivedData. Manage this information (including deleting the index and other derived data of an orphaned project) in the Organizer.

Indexing is done in the background; the Activity View indicates when indexing is being performed. Until the index is ready, some functions that require the index may not be available (for example, Open Quickly); others may have degraded performance (for example, syntax coloring of system symbols). When the index is complete these features become available immediately.

it seems to be that XCode4 and 4.1 uses crazy amounts of Ram during indexing - like, 5gb or so(!), and thus if you’re on a machine with something like 12gb, there’s no problem, but if you’re on a laptop with only 2gb or so, you’ll have some pretty severe paging going on.

How to disable indexing

Open the Terminal window , then type the following code in terminal and click enter.

defaults write com.apple.dt.XCode IDEIndexDisable 1

Now restart your xcode and enjoy better performance.

How to Enable xcode indexing

if you upgraded your machine or you want some other features to be turned on if you need indexing service, please follow the steps below.

Open the Terminal window , then type the following code in terminal and click enter.

defaults write com.apple.dt.XCode IDEIndexDisable 0

(or)

defaults delete com.apple.dt.XCode IDEIndexDisable

While you’re at it, you should delete the key you added as well:

defaults delete com.apple.dt.XCode IDEIndexEnable

Now restart the xcode now you can see the indexing will start from now on wards.

Disabling SVN & GIT in xcode

disabling SVN and Git plugins of XCode. Simply go to /Developer/Library/Xcode/PrivatePlugins

Now find IDEGit.ideplugin and IDESubversion.ideplugin

Change names of both of above plugins so that xcode will not be able to execute them in future. Now restart your xcode and enjoy better performance.

Install iOS 6 beta on your devices

2012-08-06T17:11:00.004+06:00

You're now ready to start installing betas on your devices. To do this, you'll need to use the newest version of iTunes which is 10.6.3 or you can do this through the xCode 4.5 developer preview. I recommend that developers use the xCode method while app testers are probably okay using the iTunes method unless the developer would prefer you to use xCode to submit feedback.

iTunes method

This time around there is no beta version of iTunes needed. Just make sure you're running the current version of iTunes which is 10.6.3. You can download it from Apple's website.

iTunes 10.6.3 download

Open iTunes 10.6.3 after you've installed it and plug in the device you'd like to install iOS 6 beta to.
Choose your device from the left navigation pane. You'll see a Restore button. Hold down Alt+option (or Ctrl for PC users) and click Restore.
A file browser window will pop up. Navigate to the iOS 6 beta firmware file you would like to install onto your device.
iTunes will now begin to update your device to iOS 6 beta. Let it do its thing and you're pretty much done.

Xcode method

In XCode, under software version, you'll need to choose Other version.
Then xCode will ask you to navigate to the .ipsw file that you would like to install (the beta firmware file). I typically save them on my desktop or somewhere in a folder that I can easily find.
Select it and click Restore iPhone
A warning will pop up telling you all data will be erased. Agree and your device will be restored to the beta version. You can then restore from a backup in iTunes or from iCloud like you normally would.

Either update method will get you onto the beta. It's up to you to decide what method is most appropriate for your situation.

For more Check this.

Downgrade iOS 6 Beta to iOS 5.1.1

2012-08-06T16:54:00.002+06:00

If you went ahead and installed iOS 6 beta and determined the buggy nature of the first developer release isn’t for you, it’s time to downgrade. Most developers should know how to do this already, but if not this process is easy and you’ll be back to running iOS 5.1.1 in no time at all.

Downgrading is identical on an iPhone, iPad, or iPod touch.

Turn the device off, connect it to the computer via USB, and launch iTunes
Place the iOS device into DFU mode: with the device off, hold down the Power and Home buttons together for 10 seconds then release the power button, continue holding Home button until iTunes notifies you of a device in recovery mode being detected. The devices screen should stay black as if turned off.
Restore within iTunes through either method a or b:

a: Restore from the iOS 5.1.1 backup you made prior to installing iOS 6 beta
b: Restore to iOS 5.1.1 IPSW by Option-Clicking the “Restore” button, and then restore from iCloud backup when finished

Let iTunes restore back to iOS 5.1.1, the device will reboot when finished

Typically you can’t downgrade iOS versions so easily, but because Apple is still signing iOS 5.1.1 this allows downgrading to commence with minimal effort.

How to run multiple skype account at the same time in one computer

2012-08-05T23:14:00.001+06:00

To use more than one Skype account on the same computer at the same time you need to start a new instance of Skype.

From the Windows taskbar, click Start > Run (or press the Windows and R keys on your keyboard at the same time)
In the Run window, enter the following command (include the quotes) and press OK:

"C:\Program Files\Skype\Phone\Skype.exe" /secondary

If you get an error message, copy and paste the exact command from this page and try again.

Be aware that if you have changed the installation path for Skype then you will need to enter the correct path for the Skype.exe file.

If this solution fails, you can try another option:

Find the Skype executable file (Skype.exe) in: C:\Program Files\Skype\Phone\
Right click on it and select Send to > Desktop (create shortcut)
Locate the shortcut on the desktop, then right-click on it and select Properties
In the Target field, add: /secondary. The Target field should now be "C:\Program Files\Skype\Phone\Skype.exe" /secondary
Click OK. You can now start a new instance of Skype every time you double-click the new shortcut.

PROGRAM TO FIND SQUARE ROOT OF A NUMBER - C CODE

2012-03-25T20:04:00.000+06:00

#include<stdio.h>

float SquareRoot(float num);

int main()
{
    float input, ans;

    printf("\n Enter The Number : ");
    while(scanf("%f", &input) == 1)
    {
        ans = SquareRoot(input);
        printf("\n Square Root : %f\n", ans);
    }
    return 0;
}
float SquareRoot(float num)
{
    if(num >= 0)
    {
        float x = num;
        int i;
        for(i = 0; i < 20; i ++)
        {
            x = (((x * x) + num) / (2 * x));
        }
        return x;
    }
}

Remove Powered by Blogger from your Blogger blog in new Blogger interface

2012-02-26T04:28:00.000+06:00

To Remove Powered by Blogger from your Blogger blog in new Blogger interface please visit the following link

http://www.sundeepmachado.com/2011/09/remove-powered-by-blogger-from-your.html

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

2012-02-08T00:14:00.000+06:00

/*
* @(#)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)

2012-02-08T00:09:00.000+06:00

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

2012-02-08T00:08:00.000+06:00

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

2012-02-08T00:07:00.002+06:00

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

2012-02-08T00:06:00.002+06:00

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

2012-02-08T00:05:00.003+06:00

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

2012-02-08T00:05:00.000+06:00

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

2012-02-08T00:03:00.000+06:00

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

2012-02-07T23:49:00.003+06:00

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

2012-02-07T23:49:00.000+06:00

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

2012-02-07T23:48:00.000+06:00

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

2012-02-07T23:47:00.000+06:00

#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

2012-02-07T23:46:00.000+06:00

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

2012-02-07T23:44:00.002+06:00

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

FloydWarshall MIN-MAX Distance

2012-02-07T23:43:00.003+06:00

/***
FloydWarshall MIN-MAX Distance
Author : Md.Saiful Islam
***/

#include<stdio.h>
#define MAX(aa,bb) (aa>bb?aa:bb)
#define MIN(aa,bb) (aa<bb?aa:bb)

int Road[102][102];
int Node,Edge,test,c1,c2,cost,q1,q2;

void Floyed_Warshall()
{
int k,i,j;
for(i=1;i<=Node;i++)
Road[i][i]=0;

for(k=1;k<=Node;k++)
for(i=1;i<=Node;i++)
for(j=1;j<=Node;j++)
Road[i][j] = MIN(Road[i][j], MAX(Road[i][k],Road[k][j]));
}

int main()
{
int i,kase=0,j;
while(scanf("%d %d %d",&Node,&Edge,&test)==3 && (Node || Edge || test))
{
for(i=1;i<=Node;i++)
for(j=1;j<=Node;j++)
Road[i][j]=10000;

for(i=1;i<=Edge;i++)
{
scanf("%d %d %d",&c1,&c2,&cost);
Road[c1][c2]=cost; Road[c2][c1]=cost;
}
Floyed_Warshall();

if(kase>0)
printf("\n");

printf("Case #%d\n",++kase);
for(i=1;i<=test;i++)
{
scanf("%d %d",&q1,&q2);

if(Road[q1][q2]==10000)
printf("no path\n");
else
printf("%d\n",Road[q1][q2]);
}
}
return 0;
}
/*
Input:
7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
Output:
Case #1
80
60
60

Case #2
40
no path
80
*/