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

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.


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){

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;
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...