ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1022. Генеалогическое дерево

ответ
Послано bahasdu 17 авг 2011 20:06
package topological_sorting;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader in;
    public static PrintWriter out;
    public static LinkedList<Integer> L; // list of ordered nodes
    public static LinkedList<Integer> S;// list of nodes which doesn't have
                                        // unvisited parent

    public static void main(String args[]) throws IOException {
        L = new LinkedList<Integer>();
        S = new LinkedList<Integer>();
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); // input
                                                                                    // source
        int size = (int) Integer.parseInt(in.readLine());// number of members in
                                                            // meeting
        int a[][] = new int[size][size];// view.row-numeration of
                                        // members.column-whether certain row
                                        // has member as child
        int b[][] = new int[size][size];// view2.it is as
                                        // view.column-node.rows-nodes as parent
                                        // of column node
        read(a, in, size);// fill view
        fillView2(a, b);
        setNodes(b); // nodes without incoming edges
        while (S.size() != 0) {
            int node = (int) S.remove();
            L.add(node);
            for(int j=0;j<a[node-1].length;j++){
                if(a[node-1][j]==0){
                    break;
                }else{
                    int childNode = a[node-1][j];
                    b[node-1][childNode-1]=0;
                    if(!hasParent(b,childNode)){
                        S.add(childNode);
                    }
                }
            }
        }
        showList(L);
    }

    private static boolean hasParent(int b[][],int node){
        boolean hasParent = false;
        for(int i=0;i<b.length;i++){
            if(b[i][node-1]!=0){
                hasParent=true;
                break;
            }
        }
        return hasParent;
    }
    private static void showList(LinkedList<Integer> l2) {
        for (int i = 0; i < l2.size(); i++) {
            System.out.print(l2.get(i) + " ");
        }
        System.out.println();
    }

    private static void setNodes(int[][] b) {
        for (int j = 0; j < b[0].length; j++) {
            for (int i = 0; i < b.length; i++) {
                if (b[i][j] == 0) {
                    if (i == b.length - 1) {
                        S.add(j + 1);
                    }
                } else {
                    break;
                }
            }
        }
    }

    private static void fillView2(int[][] a, int[][] b) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] == 0) {
                    break;
                } else {
                    b[i][a[i][j] - 1] = 1;
                }
            }
        }
    }

    // fill view with data
    private static void read(int[][] a, BufferedReader in, int size)
            throws IOException {
        int iterator = 0;
        while (iterator < size) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            int j = 0;
            while (tokenizer.hasMoreTokens()) {
                a[iterator][j] = (int) Integer.parseInt(tokenizer.nextToken());
                j++;
            }
            iterator++;
        }
    }

    // observe view
    public static void showArray(int a[][]) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

}