Category: Algorithm


Union-Find

Union-Find is used for make group or to find the different number of group or to find the max member of a group or to determine two things are in same or different group.

long Parent(long h1)
{
if(P[h1]==-1)
return h1;
P[h1] = Parent(P[h1]);
return P[h1];
}

for(i=1;i<=n;i++) // n number of thing
P[i]=-1;

for(i=1;i<=m;i++) // m number of connection
{
scanf(“%ld %ld”,&x,&y);
x1 = Parent(x);
y1 = Parent(y);
if(x1!=y1)
P[x1]=y1;
}

Maximum members of a group

for(i=1;i<=n;i++)
count[i]=0;

for(i=1;i<=n;i++)
count[Parent(i)]++;

max = 0;

for(i=1;i<=n;i++)

if(count[i]>max)
max = count[i];

printf(“%ld\n”,max);

To find, any two members are same or different group

for(i=1;i<=k;i++)
{
scanf(“%ld %ld”,&x,&y);
x1 = Parent(x);
y1 = Parent(y);
if(x1!=y1)
printf(“Different\n”);
else
printf(“Same\n”);
}

Kruskal

Kruskal

I suggest to use Union-Find for kruskal.

struct T
{
long x;
long y;
long weight;
};

T a[1000009];

int cmp( const void *a, const void *b )
{
T *p = (T *)a;
T *q = (T *)b;

return ( p->weight – q->weight );
}

for(i=1;i<=n;i++) // n number of node
P[i]=-1;

for(i=0;i<m;i++) // m number of edge
scanf(“%ld %ld %ld”,&a[i].x,&a[i].y,&a[i].weight);

qsort(a,m,sizeof(T),cmp);

cost = 0;

for(i=0;i<m;i++)
{
x = Parent(a[i].x);
y = Parent(a[i].y);
if(x!=y)
{
cost+=a[i].weight;
P[x]=y;
}
}

printf(“%ld\n”,cost);

Binary search

long BinarySearch(long left,long right,long value)
{
long i;
long mid = (left+right)/2;

while(left<=right)
{
if(temp[mid]==value)
break;
else if(temp[mid]<value)
left = mid+1;
else
right = mid – 1;

mid = (left+right)/2;
}

return mid;
}

LIS

LIS

This LIS complexity is nlog(n) & use binary search.

void LIS(long N)
{
long n=0,i,mid;

for(i=0;i<N;i++)
{
if(n==0)
{
temp[n]=sa[i];
tempP[n]=i;
A[i]=1;
n++;
}
else
{
mid = BinarySearch(0,n-1,sa[i]);

while(mid>0&&temp[mid]>sa[i])
mid–;

if(temp[mid]<sa[i])
{
A[i]=mid+2;
P[i]=tempP[mid];
if(mid+1>=n)
{
temp[n]=sa[i];
tempP[n]=i;
n++;
}
else if(temp[mid+1]>sa[i])
{
temp[mid+1]=sa[i];
tempP[mid+1]=i;
}
}
else if(temp[0]>sa[i])
{
temp[0]=sa[i];
tempP[0]=i;
}
}
}

}

void show(long h1)
{
if(P[h1]==-1)
printf(“%ld”,sa[h1]);
else
{
show(P[h1]);
printf(” %ld”,sa[h1]);
}
}

for(i=0;i<n;i++) // n number of the sequence
{
scanf(“%ld”,&sa[i]);
P[i]=-1;
}

LIS(n);

max = 0;
x = 0;

for(i=0;i<n;i++)
if(A[i]>max)
{
max = A[i];
x = i;
}

printf(“%ld\n”,max);
show(x);

Heap

Heap

Add a value to the min heap:

n=0; // initial value, before add any value

void AddToTheheap(long h1)
{
long root,up,k;

value[n] = h1;
n++;

root=n-1;
while(1)
{
if(root==0)
break;
up=(root-1)/2;

if(value[up]>value[root])
{
k=value[root];
value[root]=value[up];
value[up]=k;
root=up;
}
else
break;
}
}

Get a value from the min heap
taken value = value[0];
then call Reheap();

void Reheap()
{
long root,left,right,k;

value[0]=value[n-1];
n=n-1;
root=0;

while(1)
{
left=2*root +  1;
right=2*root+ 2;

if(left>=n && right>=n)
break;

if(right>=n)
{
if(value[root]>value[left])
{
k=value[root];
value[root]=value[left];
value[left]=k;
root=left;
}
break;
}
else
{
if(value[left]<value[root]&&value[left]<=value[right])
{
k=value[root];
value[root]=value[left];
value[left]=k;
root=left;
}
else if(value[right]<value[root]&&value[right]<=value[left])
{
k=value[root];
value[root]=value[right];
value[right]=k;
root=right;
}
else
break;
}
}
}

if the value of the i’th position become update(more less) in the min heap
then update heap ->
value[position] = new min value;
then call UpdateHeap(position);

void UpdateHeap(long root)
{
long up,k;

while(1)
{
if(root==0)
break;
up=(root-1)/2;

if(value[up]>value[root])
{
k=value[root];
value[root]=value[up];
value[up]=k;
root=up;
}
else
break;
}
}

Dijkstra(single source shortest path)

struct T
{
long x;
long y;
long weight;
};

T a[1000009];

scanf(“%ld %ld %ld %ld”,&node,&edge,&source,&dest);

m=0;
for(i=0;i<edge;i++)
{
scanf(“%ld %ld %ld”,&a[m].x,&a[m].y,&a[m].weight);
m++;
a[m].x=a[m-1].y;   // for bi-directional edge
a[m].y=a[m-1].x;
a[m].weight=a[m-1].weight;
m++;
}

qsort(a,m,sizeof(T),cmp);

for(i=0;i<node;i++)  // initialize
{
start[i]=-1;
dis[i] = inf;
visit[i]=0;
q_dis[i]=-1;
}

for(i=0;i<m;i++)      // connection indexing
if(start[a[i].x]==-1)
start[a[i].x]=i;

dis[   source   ]= 0;
q_x[0] = source;
q_dis[q_x[0]]=0;
n=1;

// maintain a heap, upon the dis[] & for swap, swap both q_x[] & q_dis

for(i=2;i<=node;i++)
{
vertex=-1;
while(1)
{
if(visit[q_x[0]]==0)
{
vertex=q_x[0];
visit[q_x[0]]=1;
}
if(n-1==0)
break;
ReheaP();
if(vertex!=-1)
break;
}

if(vertex==-1)
break;

if(vertex!=dest)
{
if(start[vertex]!=-1)
for(j=start[vertex];j<m;j++)
{
if(a[j].x!=vertex)
break;
if(dis[vertex]+a[j].weight<dis[a[j].y])
{
dis[a[j].y]=dis[vertex]+a[j].weight;
if(visit[a[j].y]==0)
{
if(q_dis[a[j].y]==-1)
{
AddToTheheap(a[i].y); // add node a[i].y to the heap
}
else
UpdateHeap(q_dis[a[j].y]); // update the position of a[j].y node
}

}
}
}
else
break;

if(n==0)
break;

}

if(dis[dest]==inf)
printf(“unreachable\n”);
else
printf(“%ld\n”,dis[dest]);

You can consider a problem like this, you are in node 1, and you have to visit node 2 5 & 10.  Now, you have to fine the minimum cost for this operation. You can called it DP also.

you have to visit l number of node, like l = 3. then node[] = 2, 3, 4
& your source is 1. now you have to find the minimum cost of the tour.

C[][] = cost matrix of the nodes.
P[0]=1;
for(i=1;i<=15;i++ )
{
P[i] = P[i-1]*2;
}

source = 1;
for(i=0;i<=P[l];i++)
{
for(j=0;j<l;j++)
{
bit[i][j] = MAX;
}
}

for(i=0;i<l;i++)
{
if( C[ source ][ node[i] ]!=MAX )
{
bit[ P[i] ][i] = C[ source ][ node[i] ];
}
}

for(i=0;i<P[l];i++)
{
for(j=0;j<l;j++)
{
if( bit[i][j]!=MAX )
{
for(k=0;k<l;k++)
{
if( (i%P[k+1])/P[k]==0 )
{
if( C[node[j]][node[k]]!=MAX )
{
if( bit[ i+P[k] ][k] > bit[i][j] + C[node[j]][node[k]] )
{
bit[ i+P[k] ][k] = bit[i][j] + C[node[j]][node[k]];
}
}
}
}
}
}
}

int res = MAX;

for(i=0;i<l;i++)
if(bit[P[l]-1][i]!=MAX)
if(res > bit[P[l]-1][i])
res = bit[P[l]-1][i];

printf(“%d\n”,res);

For reduce some complexity, you also can use bfs in bit mask.

BFS

BFS

visit[]={0};

A[][] = connection matrix.

n = number of nodes, from 1 to n.
source = 1;
temp[0]=source;
visit[ source ]=1;
N = 0;
M = 1;

while(N!=M)
{
for(i=1;i<=n;i++)
if(A[temp[N]][i]==1&&visit[i]==0)

// A[temp[N]][i]==1 means node temp[N] & i are connected. visit[i]==0 means node i has not visited
{
visit[i]=1;
temp[M]=i;
M++;
}
N++;
}

for(i=0;i<M;i++)
printf(“%ld “,temp[i]);

DFS

DFS

void DFS(long node)
{
long i;
printf(“%ld “,node);
visit[node]=1;

for(i=1;i<=n;i++)
if(visit[i]==0&&A[node][i]==1)
DFS(i);

}

visit[]={0};

A[][] = connection matrix.

n = number of nodes, from 1 to n.

source = 1;
DFS(source);

It is possible to represent a graph by bi-coloring if, every neighbor nodes color is different than itself.

We can use bfs or dfs for bicoloring. example is using dfs.

void BiColor(long node)
{
long i;

for(i=1;i<=n;i++)
if(A[node][i]==1)
{
if(color[i]==-1)
{
color[i] = (color[node] + 1 )%2;
BiColor(i);
}
else if(color[i]==color[node])
yes = 0;

if(yes==0)
break;
}
}

color[]={-1};

A[][] = connection matrix.

n = number of nodes, from 1 to n.
yes = 1;
for(i=1;i<=n;i++)
if(color[i]==-1)
{
color[i]=0;
BiColor(i);
}

if(yes==1)
printf(“possible\n”);
else
printf(“not possible\n”);