Algorithm

A very short and neat code for Union-Find

Posted on August 13, 2008. Filed under: Algorithm |

This is the Union-Find code that my team use, we call it two-liner, because there’s only two lines responsible for the real stuff

int parent[N];

int find(int u){
return u == parent[u] ? u : parent[u] = find(parent[u]);
}

int join(int u,int v){
parent[find(u)] = find(v);
}

// init
for(int i=0;i

Advertisements
Read Full Post | Make a Comment ( None so far )

Minimum Weighted Aborescence (Directed MST)

Posted on August 13, 2008. Filed under: Algorithm, Graph, UVA | Tags: , , |

Source code for my AC solution to UVA 11183 with 0.14s which is an implementation of directed minimum spanning tree algorithm from here.

#include
#include
#include
#include

using namespace std;

#define N 1002

int pred[N],mins[N],parent[N];
int adjc[N],radjc[N];
int adj[N][N],radj[N][N],cost[N][N];
bool visit[N],cycle[N];
int mine;

int find(int u){
return parent[u]==u?u:parent[u]=find(parent[u]);
}

void join(int u,int v){
parent[find(v)]=find(u);
}

bool dfs(int r,int u){
if(visit[u])return r==u;visit[u]=true;
for(int i=0;i=0){
int k=pred[i]; adj[k][adjc[k]++]=i;
if(first) mc+=mins[i];
}
first = false;
memset(cycle,0,sizeof(cycle));
memset(visit,0,sizeof(visit));
int inc=mine=0x7fffffff;
bool hc=false;
for(int i=0;i Read Full Post | Make a Comment ( None so far )


Liked it here?
Why not try sites on the blogroll...