ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1022. Genealogical Tree

ответ
Posted by bahasdu 17 Aug 2011 20:06
package topological_sorting;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
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 {
// 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
fillView2(a, b);
setNodes(b); // nodes without incoming edges
while (S.size() != 0) {
int node = (int) S.remove();
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)){
}
}
}
}
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) {
}
} 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
throws IOException {
int iterator = 0;
while (iterator < size) {
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();
}
}

}