2

こんにちは、私はこの問題を解決しようとしていましたhttp://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=813そして、トポロジーソートの問題のすべての解決策を取得したいことに気付きました。可能な解決策を1つだけ取得してください。これが私のコードですhttp://ideone.com/IiQxiu

static ArrayList<Integer> [] arr;  
static int visited [];
static Stack<Integer> a = new Stack<Integer>();
static boolean flag=false;

public static void graphcheck(int node){  //method to check if there is a cycle in the graph
    visited[node] = 2;
    for(int i=0;i<arr[node].size();i++){
        int u =arr[node].get(i);
        if(visited[u]==0){
            graphcheck(u);
        }else if(visited[u]==2){
                flag=true;
                return; 
            }
    }
    visited[node] = 1;
}

public static void dfs2(int node){            //method to get one possible topological sort which I want to extend to get all posibilites
    visited[node] = 1;
    for(int i=0;i<arr[node].size();i++){
        int u =arr[node].get(i);
        if(visited[u]==0){
            dfs2(u);
        }   
    }
    a.push(node);
}

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tc = Integer.parseInt(br.readLine());
    for(int k=0;k<tc;k++){
        br.readLine();

        String h[]= br.readLine().split(" ");
        int n= h.length;
        arr=new ArrayList[n];
        visited = new int[n];
        for( int i = 0; i < n; i++) {
            arr[ i] = new ArrayList<Integer>();
        }
        String q[]=br.readLine().split(" ");
        int y=q.length;
        for(int i=0;i<y;i++){
            int x=0;
            int z=0;
            for(int j=0;j<n;j++){
                if(q[i].charAt(0)==h[j].charAt(0)){
                    x=j;
                }else if(q[i].charAt(2)==h[j].charAt(0)){
                    z=j;
                }
            }
            if(q[i].charAt(1)=='<'){
                        arr[x].add(z);
            }
        }
        for(int i=0;i<n;i++){
            if(visited[i]==0)
                graphcheck(i);
        }
        if(flag){
            System.out.println("NO");
        }else{
        a.clear();
        Arrays.fill(visited, 0);
        for(int i=0;i<n;i++){
            if(visited[i]==0){
                dfs2(i);
            }   
        }
        int z= a.size();
        for(int i=0;i<z;i++){
            int x =a.pop();
            System.out.print(h[x]+" ");
        }
        System.out.println();
    }


}
}
4

3 に答える 3

0

将来の視聴者のためのソリューションの追加:

トポロジカル ソートのすべてのソリューションを出力するには、次のアプローチに従います。

  1. すべての頂点をマークなしで初期化します。

  2. ここで、マークされておらず、次数がゼロの頂点を選択し、これらすべての頂点の次数を 1 減らします (エッジの削除に対応)。

  3. この頂点をリストに追加し、再帰関数を再度呼び出してバックトラックします。

  4. 関数から戻った後、marked、list、および indegree の値をリセットして、他の可能性の列挙を行います。

以下のコード --

class GraphAllTopSorts{
    int V;  // No. of vertices
    LinkedList<Integer>[] adj;  //Adjacency List
    boolean[] marked;   //Boolean array to store the visited nodes
    List<Integer> list;
    int[] indegree; //integer array to store the indegree of nodes

    //Constructor
    public GraphAllTopSorts(int v) {
        this.V=v;
        this.adj = new LinkedList[v];
        for (int i=0;i<v;i++) {
            adj[i] = new LinkedList<Integer>();
        }
        this.indegree = new int[v];
        this.marked = new boolean[v];
        list = new ArrayList<Integer>();
    }

    // function to add an edge to graph
    public void addEdge(int v, int w){
        adj[v].add(w);
        // increasing inner degree of w by 1
        indegree[w]++;
    }

    // Main recursive function to print all possible topological sorts
    public void alltopologicalSorts() {
        // To indicate whether all topological are found or not
        boolean flag = false;

        for (int w=0;w<V;w++) {

            // If indegree is 0 and not yet visited then
            // only choose that vertex
            if (!marked[w] && indegree[w]==0) {
                marked[w] = true;
                Iterator<Integer> iter = adj[w].listIterator();
                while(iter.hasNext()) {
                    int k = iter.next();
                    indegree[k]--;
                }

                // including in list
                list.add(w);
                alltopologicalSorts();

                // resetting marked, list and indegree for backtracking
                marked[w] = false;
                iter = adj[w].listIterator();
                while(iter.hasNext()) {
                    int k = iter.next();
                    indegree[k]++;
                }
                list.remove(list.indexOf(w));

                flag = true;
            }
        }

        // We reach here if all vertices are visited.
        // So we print the solution here
        if (!flag) {
            for (int w=0;w<V;w++) {
                System.out.print(list.get(w) + " ");
            }
            System.out.print("\n");
        }
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        // Create a graph given in the above diagram
        GraphAllTopSorts g = new GraphAllTopSorts(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("All Topological sorts");

        g.alltopologicalSorts();
    }
}

ソース: http://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/

于 2016-07-06T16:59:31.837 に答える