Java实现Labeling Balls(拓扑排序的应用)

1 问题描述

给出一些球，从1_{N编号，他们的重量都不相同，也用1}N标记加以区分（这里真心恶毒啊，估计很多WA都是因为这里），然后给出一些约束条件，< a , b >要求编号为 a 的球必须比 b 轻，现在要求按编号升序输出每个球的重量，如果有多种解，输出字典序最小的那个。

例如：

input：

5 4

5 1

4 2

1 3

2 3

output：

2 4 5 3 1

package com.liuzhen.practice;

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

    public static int count;   //顶点的编号

    public static int[] degree;   //计算顶点的入度

    public static ArrayList<edge>[] map;  //表示图

    public static ArrayList<String> result1 = new ArrayList<String>();

    static class edge {

        public int a;    //边的起点

        public int b;    //边的终点

        public edge(int a, int b) {

            this.a = a;

            this.b = b;

        }

    }

    @SuppressWarnings("unchecked")

    public void init(int n) {

        count = n;

        degree = new int[n + 1];

        map = new ArrayList[n + 1];

        for(int i = 0;i <= n;i++) {

            map[i] = new ArrayList<edge>();

            degree[i] = 0;

        }

        return;

    }

    public String getResult() {

        String result = "";

        int[] ans = new int[degree.length];

        while(count >= 1) {

            int i = degree.length - 1;

            for(;i >= 1;i--) {

                if(degree[i] == 0) {

                    ans[i] = count--;

                    degree[i]--;

                    for(int j = 0;j < map[i].size();j++)

                        degree[map[i].get(j).b]--;

                    break;

                }

            }

            if(i == 0)   //此时给定图存在回环

                return "-1";

        }

        StringBuilder temp = new StringBuilder("");

        for(int i = 1;i < ans.length;i++) {

            temp.append(ans[i]);

            if(i != ans.length - 1)

                temp.append(" ");

        }

        result = temp.toString();

        return result;

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        int t = in.nextInt();     //要输入图的个数

        while(t > 0) {

            t--;

            int n = in.nextInt();

            test.init(n);

            int k = in.nextInt();   //输入图的边的个数

            for(int i = 0;i < k;i++) {

                int a = in.nextInt();

                int b = in.nextInt();

                boolean judge = true;

                for(int j = 0;j < map[b].size();j++) {   //检查重复边

                    if(map[b].get(j).b == a){

                        judge = false;

                        break;

                    }

                }

                if(judge && a != b) {

                    map[b].add(new edge(b, a));

                    degree[a]++;  //顶点a的入度自增1

                }

            }

            result1.add(test.getResult());

        }

        for(int i = 0;i < result1.size();i++) {

            System.out.println(result1.get(i));

        }

    }

}

运行结果：

4

1

2

3

3

5

1

1

8

1

8

4 5 3 1

1 6 2 7 8 3 4 9 10

巴特西

Java实现Labeling Balls(拓扑排序的应用)

最新文章

热门文章