Archive | Algorithm codes RSS feed for this section

29 August 2010 Comments Off

LIS


#include<stdio.h>
#define MAXN 100

int A[MAXN], N;
int L[MAXN], P[MAXN];

void printPath(int x) {
if(P[x] == -1) {
printf("%d",x);
return;
}
printPath(P[x]);
printf(" %d",x);
}

int doLIS() {
int i, j;
int longest = 0, last = 0;
for(i = 1; i<=N; i++) {
int max = 0;
int parent = -1;
for(j = i-1; j>=0; j--) {
if(A[i] > A[j]) {
if(L[j] > max) {
max = L[j];
parent = j;
}
}
}
L[i] = max+1;
P[i] = parent;
if(L[i] > longest) {
longest = L[i];
last = i;
}
}
printf("LIS : ");
printPath(last);
puts("");
printf("Length: %d\n",longest);
return longest;
}

int main() {
int i;
while(scanf("%d",&N) == 1) {
A[0] = 0;
for(i = 1; i<= N; i++) {
scanf("%d",&A[i]);
}
doLIS();

}
return 0;
}
Tags: ,
29 August 2010 Comments Off

BFS algorithm in C++

/*

BFS algorithm in C++

*/
#include<stdio.h>
#define maxn 101

int Q[maxn];
int top ,back;
int Node, Edge;

char link[maxn][maxn];
char Fg[maxn];
int Path[maxn];

void Ini() {
int i, j;
for(i = 1; i<= Node; i++) {
for(j = 1; j<= Node; j++) {
link[i][j] = 0;
}
Path[i] = i;
Fg[i] = 0;
}
}

void Insert(int n) {
Q[back++] = n;
back %= maxn;
}

int Pop() {
int n = Q[top++];
top %= maxn;
return n;
}

int isEmpty() {
if(top == back) return 0;
return 1;
}

void PrintPath(int n) {
if(n == Path[n]) {
printf("%d",n);
return;
}
PrintPath(Path[n]);
printf(" %d",n);
}

int BFS(int s, int ter) {
int u, v, i;
Insert(s);
Fg[s] = 1;
while(isEmpty() == 1) {
v = Pop();
if(v == ter) {
PrintPath(v);
return 1;
}

for(i = 1; i<= Node; i++) {
if(link[v][i] == 1 && Fg[i] == 0)  {
Fg[i] = 1;
Insert(i);
Path[i] = v;
}
}
}
return -1;
}

void main() {
int i, u, v;
scanf("%d%d",&Node,&Edge);
Ini();
while(Edge--) {
scanf("%d%d",&u,&v);
link[u][v] = link[v][u] = 1;
}
scanf("%d%d",&u,&v);
BFS(u,v);
printf("\n");
}

/*
4 5
1 2
2 3
1 3
3 4
2 4
1 4
*/
Tags: ,
29 August 2010 Comments Off

Prim’s Algorithm- MST

#include<iostream.h>
#include<queue>
#include<vector>
#define INF 100000

using namespace std;

struct edge {
vector<int>Adj;
vector<int>Cost;
};

struct node{
int x, y;
};

edge Ed[100];
int N, E;
int key[100];
char F[100];
int P[100], Cost;
int SS[100][100];

class comp{
public:
bool operator() ( const node &a, const node &b)
{
return a.y > b.y;
}
};

void CT(int u) {
if(F[u] == 1 || u == 1) return;
F[u] = 1;
if(P[u] == -1) return;
Cost += SS[u][P[u]];
CT(P[u]);
}

int Prim() {
int i, j, u, v, c,cost;
Cost =  0;
priority_queue<node, vector<node>, comp> Q;
node temp, dum;
for(i = 1; i<= N; i++)
key[i] = INF;
key[1] = 0;
temp.x = 1;
temp.y = 0;
Q.push(temp);
P[1] = -1;
while(!Q.empty()) {
temp = Q.top();
Q.pop();
u = temp.x;
F[u] = 1;
for(i = 0; i<Ed[u].Adj.size(); i++) {
v = Ed[u].Adj[i];
c = Ed[u].Cost[i] + temp.y;
if(F[v] == 0) {
if(key[v] > c) {
dum.x = v;
dum.y = c;
key[v] = c;
P[v] = u;
Q.push(dum);
}
}
}
}
for(i = 1; i<= N; i++) F[i] = 0;
for(i = 1; i<= N; i++) {
if(F[i] == 0)
CT(i);
}
return Cost;
}

void main() {
int c, u, v, n;
cin>>N>>E;
n = E;
while(n--) {
cin>>u>>v>>c;
Ed[u].Adj.push_back(v);
Ed[u].Cost.push_back(c);
Ed[v].Adj.push_back(u);
Ed[v].Cost.push_back(c);
SS[u][v] = SS[v][u] = c;
}
cout<<Prim()<<endl;
}
Tags: ,
29 August 2010 Comments Off

MST(Kruskal’s Algorithm)


/*
MST(Kruskal's)
*/

#include<iostream.h>
#include<stdlib.h>

#define MAXN 102

int P[MAXN], Rank[MAXN];

int Node, edg, Cost;

struct edge {
int u, v;
int cost;
};

edge Edge[MAXN*MAXN];
edge Path[MAXN];

int com(const void *xy, const void *xz) {
edge *x = (edge*)xy;
edge *y = (edge*)xz;
return (x->cost - y->cost);
}

void In() { // initializing parent and rank for each node
int i;
for(i = 1; i<= Node; i++) {
P[i] = i;
Rank[i] = 1;
}
}

int Find(int n) { // find the parent of a node
if(P[n] != n)
P[n] = Find(P[n]);
return P[n];
}

void Link(int x, int y) { // joining the nodes
if(Rank[x] > Rank[y]) {
P[y] = x;
}
else {
P[x] = y;
if(Rank[x] == Rank[y])
Rank[y]++;
}
}

void Kruscal() {
int x, y, total = 0;
Cost = 0;
for(int i = 0; i<edg; i++) {
x = Find(Edge[i].u);
y = Find(Edge[i].v);
if(x != y) { // if not cycle

Path[total++] = Edge[i];
Link(x,y); // join those node
Cost += Edge[i].cost;
if(total == Node - 1) break; // already taken all nodes ?
}
}
}

void Cal() {
qsort(Edge,edg,sizeof(edge),com); // sorting the edges respect to cost
Kruscal();
cout<<"Total Cast :"<<Cost<<endl;
for(int i = 0; i<Node-1; i++) // printing the path
cout<<Path[i].u<<" "<<Path[i].v<<" "<<Path[i].cost<<endl;
}

void main() {
int i;
while(cin>>Node>>edg) { // reading number of node and edge
In();
for(i = 0; i<edg; i++)  // reading each edate with cost
cin>>Edge[i].u>>Edge[i].v>>Edge[i].cost;
Cal();
}
}