uva: 10305 Ordering Tasks ( Topological sort )

10305 Ordering Tasks ( Topological sort )

Problem and solution –


import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Queue;


class Main_10305_OrderingTasks {
	
	static String readInputLine() throws IOException
	{

		int byt,index=0;
		byte[] bytes= new byte[255];

		while(true)
		{
			byt = System.in.read();
			if(byt==-1 || byt =='\n') break;
			bytes[index++] += byt;
		}

		if(bytes.length==0) return null;

		return new String(bytes);
	}

	public static void main(String[] args) throws IOException {
		String line;
		String[] tempArr;
		int vertex, edge, u,v;
		int[][] graph;
		int[] indegree;
		StringBuilder order;
		Queue q = new PriorityQueue(100+1);

		while(true)
		{

			line = readInputLine();
			if(line == null) break;

			tempArr = line.trim().split(" ");
			vertex = Integer.parseInt(tempArr[0]);
			edge = Integer.parseInt(tempArr[1]);

			if(vertex ==0) break;

			graph = new int[vertex+2][vertex+2];
			indegree = new int[vertex+1];
			order = new StringBuilder();
			
			for(int i=1; i<=edge; i++)
			{
				tempArr=  readInputLine().trim().split(" ");
				u = Integer.parseInt(tempArr[0]);
				v = Integer.parseInt(tempArr[1]);

				graph[u][v] = 1;
				indegree[v] +=1;
			}	

			//start processing tasks/vertex
			q.clear();
			while(true)
			{
				u=v=-1;
				for(int i=1; i<=vertex; i++)
				{
					if(indegree[i] == 0 )
					{		
						q.add(i);
						indegree[i] = -1; //task in queue
						order.append(i+" ");//output data											
					}
				}
				
				//if no task to process then break
				if(q.isEmpty()) break;
				u = q.poll();
				//reduce indegree from source/u task to dependent tasks
				for(v=0; v <= vertex; v++)
				{
					if(graph[u][v]==1) 
					{
						graph[u][v] = 0;
						indegree[v] -= 1;
					}
				}
			}
			//output tasks order
			System.out.println(order.toString().trim() );
			
		}
		//System.out.println(str);
	}

}




/*

Sample Input

5 4
1 2
2 3
1 3
1 5
0 0
Sample Output

1 4 2 5 3

*
*/

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: