Saturday 15 November 2014

Topological Sorting - SPOJ pblm PFDEP Solution in Java

Topological sorting: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Applications:
Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization

Reference Video:
https://www.youtube.com/watch?v=W9cfpsPJwhc&index=50&list=PLLH73N9cB21W1TZ6zz1dLkyIm50HylGyg

Problem from SPOJ:
http://www.spoj.com/problems/PFDEP/

Solution :

public void solve(int testNumber, PFDEPInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int n = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[n];
        for(int i=0;i<n;i++) alist[i] = new ArrayList<Integer>();
        int[] indegree = new int[n];

        int m = in.nextInt();
        while(m-- > 0) {
            int v = in.nextInt()-1;
            int k = in.nextInt();
            indegree[v] += k;
            while(k-->0) {
                alist[in.nextInt()-1].add(v);
            }
        }
        ArrayList<Integer> result = TopoSort(alist,indegree);
        int i=0;
        for(i=0;i<result.size()-1;i++) out.print(result.get(i) + " ");
        out.print(result.get(i));
    }

    public ArrayList<Integer> TopoSort(ArrayList<Integer>[] alist,int[] indegree){
        Queue<Integer> q = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        boolean[] visited = new boolean[alist.length];

        for(int i=0;i<indegree.length;i++) {
            if(indegree[i] == 0) { q.add(i);  visited[i] = true; break;}
        }

        while(!q.isEmpty()) {
            int u = q.poll();
            result.add(u+1);

            for(int i=0;i<alist[u].size();i++) {
                int v = alist[u].get(i);
                indegree[v]--;
            }

            for(int i=0;i<alist.length;i++) {
                if(!visited[i] && indegree[i] == 0) { q.add(i); visited[i] = true; break;}
            }
        }
        return result;
    }
}

Time Complexity: O(V+E) - V - no of vertices and E - no of Edges

No comments:

Post a Comment