import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;
import java.util.Arrays;

public class SpanningTree {
    int SIZE;
    int GROUPS;   
    int EDGE_COUNT,ROOT;
    int[][] EDGE=new int[100][2];   //list of edges in the tree
    int[] G=new int[100]; //list or groups
    int[][] P=new int[100][2]; //predecessors: (dist from root, neighbor nearer to root) 
    double[] X=new double[10000]; //for sorting purposes
    double[][] WEIGHT=new double[100][100];  //list of graph weights
    int[] VALENCE=new int[100];

    public SpanningTree() {}


    /**fixing lists*/

    public static int[] trim(int[] list1,int count) {
	int[] list2=new int[count];
	for(int i=0;i<count;++i) list2[i]=list1[i];
	return(list2);
    }

    public static int[] reverse(int[] list1,int count) {
	int[] list2=new int[count];
	for(int i=0;i<count;++i) list2[i]=list1[count-1-i];
	return(list2);
    }


    /**The purpose of these routines is to get Java's
       double sorter to lexicographically sort triples
       of the form (d,i,j) where d is a double and
       i,j are indices.  In practice, d is the weight
       of the edge connecting (i) to (j).*/

    public static double encode(double d,int i,int j) {
	double x=d+1;
	x=x*Math.pow(10,8);
	x=Math.floor(x);
	int ii=i+100;
	int jj=j+100;
	x=x+1.0*ii/1000+1.0*jj/1000000;
	return(x);
    }

    public static double getValue(double x) {
	double d=Math.floor(x)/Math.pow(10,8);
	return(d-1);
    }

    public static int[] getIndex(double x) {
	double y0=x-Math.floor(x);
	double y1=1000*y0;
	double y2=Math.floor(y1+.5);
	double y3=y1-y2;
	double y4=Math.floor(1000*y3+.5);
	int i=(int)(y2);
	int j=(int)(y4);
	int[] k ={i-100,j-100};
	return(k);
    }



    /**This routine converts a list of points in the
       plane to an array of weights*/

    public double[][] pointsToWeights(Complex[] Z,int COUNT) {
	double[][] W=new double[COUNT][COUNT];
	for(int i=0;i<COUNT;++i) {
	    for(int j=0;j<COUNT;++j) {
		double dist=Complex.dist(Z[i],Z[j]);
		W[i][j]=dist;
	    }
	}
	return(W);
    }



    /**Here W is the list of weights and S is the size*/

    public void initialize(double[][] W,int S) {

	SIZE=S;
	for(int i=0;i<S;++i) {
	    for(int j=0;j<S;++j) {
		WEIGHT[i][j]=W[i][j];
	    }
	}

	int c=S*(S-1)/2;
	X=new double[c];
	int count=0;
	for(int i=0;i<S;++i) {
	    for(int j=i+1;j<S;++j) {
		X[count]=encode(WEIGHT[i][j],i,j);
		++count;
	    }
	}
	Arrays.sort(X);
	for(int i=0;i<SIZE;++i) {
           G[i]=-1;
           P[i][0]=-1;
           P[i][1]=-1;
	}
	GROUPS=0;
	EDGE_COUNT=0;
    }


    /*starts with a recommended root*/

    public void getTree() {
	int count=0;
	while(count<X.length) {
	  int[] k=getIndex(X[count]);
	  boolean test=join(k[0],k[1]);
	  ++count;
	}
      	computeValences();
	ROOT=0;
	setPredecessors();
    }




    public void assignEdge(int i,int j) {
	int e=EDGE_COUNT;
	EDGE[e][0]=i;
	EDGE[e][1]=j;
	++EDGE_COUNT;
    }

    public boolean join(int i,int j) {

	//creates a new component
	if((G[i]==-1)&&(G[j]==-1)) {
	    G[i]=GROUPS;
	    G[j]=GROUPS;
	    ++GROUPS;
	    assignEdge(i,j);
	    return(true);
	}

	//joins i to group j
	if((G[i]==-1)&&(G[j]!=-1)) {
	    G[i]=G[j]; 
            assignEdge(i,j);
	    return(true);
	}

	//joins j to group i
	if((G[i]!=-1)&&(G[j]==-1)) {
	    G[j]=G[i]; 
            assignEdge(i,j);
	    return(true);
	}

	//joins group j to group i
	if((G[i]!=-1)&&(G[j]!=-1)&&(G[i]<G[j])) {
	    int mark=G[j];
	    G[j]=G[i];
	    for(int k=0;k<SIZE;++k) {
		if(G[k]==mark) G[k]=G[i];
		if(G[k]>mark) --G[k];
	    }
	    --GROUPS;  
            assignEdge(i,j);
	    return(true);
	}

	//joins group i to group j
	if((G[i]!=-1)&&(G[j]!=-1)&&(G[j]<G[i])) {
	    int mark=G[i];
	    G[i]=G[j];
	    for(int k=0;k<SIZE;++k) {
		if(G[k]==mark) G[k]=G[j];
		if(G[k]>mark) --G[k];
	    }
	    --GROUPS;  
            assignEdge(i,j);
	    return(true);
	}
	return(false);
    }


    public void computeValences() {
	for(int i=0;i<SIZE;++i) VALENCE[i]=0;
	for(int i=0;i<SIZE-1;++i) {
            ++VALENCE[EDGE[i][0]];
            ++VALENCE[EDGE[i][1]];
	}
    }

    public int[] pathToRoot(int k) {
	int k0=k;
	int[] q0=new int[SIZE];
	int count=0;
	while(k0!=-1) {
	    q0[count]=k0;
	    k0=P[k0][1];
	    ++count;
	}
	return(trim(q0,count));
    }


    /**These routines assign the following numbers:
       P[p][0] is the distance to the root.
       P[p][1] is the index of the neighbor of p that is nearer the root.
    **/


    public void setPredecessors() {
        int k=ROOT;
        P[ROOT][0]=0;
        boolean test=true;
        while(test==true) {
          test=setPredecessorsStep();
        }
    }

    public boolean setPredecessorsStep() {
        boolean test=false;
        for(int i=0;i<SIZE-1;++i) {
            int p=EDGE[i][0];
            int q=EDGE[i][1];
            if((P[p][0]==-1)&&(P[q][0]!=-1)) {
                  P[p][0]=P[q][0]+1;
                  P[p][1]=q;
                  test=true;
            }
            if((P[q][0]==-1)&&(P[p][0]!=-1)) {
                  P[q][0]=P[p][0]+1;
                  P[q][1]=p;
                  test=true;  
            }
        }
        return(test);
    }


    /**gets all neighbors*/

    public int[] getNeighbors(int k) {
	int[] n=getAwayNeighbors(k);
	if(k==ROOT) return(n);
	int[] m=new int[n.length+1];
	for(int i=0;i<n.length;++i) m[i+1]=n[i];
	m[0]=P[k][1];
	return(m);
    }



    /**Gets the neighbors, pointing away from the root, sorted by
       weight of the connecting edge.*/

    public int[] getAwayNeighbors(int k) {
	int[] n0=new int[SIZE];
	int count=0;
	for(int i=0;i<SIZE;++i) {
	    if(P[i][1]==k) {
		n0[count]=i;
		++count;
	    }
	}
	int[] n1=new int[count];
	double[] w=new double[count];
	for(int i=0;i<count;++i) {
	    int t=n0[i];
	      w[i]=encode(WEIGHT[k][t],k,t);
	}
	Arrays.sort(w);
	for(int i=0;i<count;++i) {
	    int[] t=getIndex(w[i]);
	    n1[i]=t[1];
	}
	return(n1);
    }

    public double getTreeWeight() {
	double d=0;
	for(int i=0;i<SIZE-1;++i) {
	    d=d+WEIGHT[EDGE[i][0]][EDGE[i][1]];
	}
	return(d);
    }


}