UVA – 10305 – Ordering Tasks

  • ID : UVA – 10305 – Ordering Tasks
  • Language : Java , C++
  • Status : Accepted – Accepted
  • Type : Topological Sort.
  • Time : 6 Hours.
  • Solution :
          1. Source Removal Method or DFS
          2. Calculate in Degree.
          3. Use a queue and insert at first all edges with 0 in Degree those who must be finished first.
          4. Dequeue every time a node and decrease the in-degree of all it’s neighbours as this node is considered to be removed from the queue or the task is done
          5. each time you decrease the degree of the node. check if this task is available now ( i.e it’s degree is zero that means that all of it’s dependencies is already finished.
  • Problems :
          1. Check for special cases in the input. the m could be a zero and that what stopped me for 6 hours and I don’t know what’s wrong with my solution. I discovered that I have to remove the  m!=0  condition from the while loop statement.
          2. I wasn’t able to submit the DFS solution don’t know what’s the reason. but I decided to solve more problems for this period and come to this later
  • Code :
import java.io.DataInputStream;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	Parser in = new Parser(System.in);
	//Scanner in = new Scanner(System.in);
	int[] x, y;
	ArrayList<Edge<Double>> edges;
	int constructed, N;
	int old;
	ArrayList<String> sol;

	public static void main(String[] args) throws Exception {
		Main p = new Main();
		p.readInput();
		System.exit(0);
	}

	public void solveCase() {

		Collections.sort(edges);
		sol = new ArrayList<String>();
		int newEdges = 0;
		for (Edge<Double> e : edges) {
			if (old + newEdges >= N - 1)
				break;

			if (find(e.a) != find(e.b)) {
				union(find(e.a), find(e.b));
				newEdges++;
				sol.add((e.a + 1) + " " + (e.b + 1));
			}
		}

		if (newEdges == 0)
			{System.out.println("No new highways need"); }
		else {
			for(String s : sol){
				System.out.println(s);
			}
		}
	}

	public double distance(int i, int j) {
		int dx = (x[i] - x[j]) * (x[i] - x[j]);
		int dy = (y[i] - y[j]) * (y[i] - y[j]);
		return Math.sqrt(dx + dy);
	}

	public void readInput() throws Exception {

		int T = in.nextInt();

		while (T-- != 0) {

			readCase();
			solveCase();
			if (T > 0)
				System.out.println("");
		}
	}

	public void readCase() throws Exception {
		edges = new ArrayList<Edge<Double>>();
		N = in.nextInt();
		x = new int[N];
		y = new int[N];
		p = new int[N];
		rank = new int[N];

		for (int i = 0; i < N; i++)

			p[i] = i;

		for (int i = 0; i < N; i++) {
			x[i] = in.nextInt();
			y[i] = in.nextInt();
			for (int j = 0; j < i; j++) {
				edges.add(new Edge<Double>(i, j, distance(i, j)));
			}
		}

		constructed = in.nextInt();
		old = 0;
		for (int i = 0; i < constructed; i++) {
			int a = in.nextInt() - 1, b = in.nextInt() - 1;
			if (find(a) != find(b)) {
				union(find(a), find(b));
				old++;
			}
		}

	}

	class Parser
	{
	   final private int BUFFER_SIZE = 1 << 16;

	   private DataInputStream din;
	   private byte[] buffer;
	   private int bufferPointer, bytesRead;

	   public Parser(InputStream in)
	   {
	      din = new DataInputStream(in);
	      buffer = new byte[BUFFER_SIZE];
	      bufferPointer = bytesRead = 0;
	   }

	   public int nextInt() throws Exception
	   {
	      int ret = 0;
	      byte c = read();
	      while (c <= ' ') c = read();
	      boolean neg = c == '-';
	      if (neg) c = read();
	      do
	      {
	         ret = ret * 10 + c - '0';
	         c = read();
	      } while (c > ' ');
	      if (neg) return -ret;
	      return ret;
	   }

	   private void fillBuffer() throws Exception
	   {
	      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
	      if (bytesRead == -1) buffer[0] = -1;
	   }

	   private byte read() throws Exception
	   {
	      if (bufferPointer == bytesRead) fillBuffer();
	      return buffer[bufferPointer++];
	   }
	}

	class Edge<T> implements Comparable<Edge<T>> {
		int a, b;
		T w;

		public Edge(int a, int b, T w) {
			this.a = a;
			this.b = b;
			this.w = w;
		}

		@SuppressWarnings("unchecked")
		@Override
		public int compareTo(Edge<T> o) {
			return ((Comparable<T>) w).compareTo(o.w);
		}

		public String toString() {
			return "( " + a + " <-> " + b + " )  Cost: " + w;
		}
	}

	int p[];
	int rank[];

	public int find(int a) {
		if (a == p[a])
			return a;
		return p[a] = find(p[a]);
	}

	public void union(int a, int b) {
		if (a == b)
			return;
		if (rank[a] > rank[b]) {
			p[b] = a;
		} else {
			p[a] = b;
			if (rank[a] == rank[b])
				rank[b]++;
		}
	}

}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: