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

What's wrong with my Topological Sorting?
Posted by Peter P 23 May 2014 15:43
I got WA#1 :(
What's wrong bros?

===============================================================
static int speakerCount = 0;

static void solve() throws IOException {
final int N = nextInt();

// graph[i][j] = true: i-th is parent of j-th
final boolean[][] graph = new boolean[N + 1][N + 1];

for (int line = 1; line <= N; line++) {
int parent = nextInt();

if (parent == 0) {
continue;
}

int child = nextInt();
while (0 < child) {
graph[parent][child] = true;

child = nextInt();
}
}

StringBuilder speakerList = new StringBuilder();
final boolean[] visitedNodes = new boolean[N + 1];

while (speakerCount < N) {
for (int node = 1; node <= N; node++) {
if (!visitedNodes[node]) {
visit(node, visitedNodes, speakerList, graph);

break;
}
}
}

out.println(speakerList.toString().trim());
}

private static void visit(int node, boolean[] visitedNodes,
StringBuilder speakerList, boolean[][] graph) {

// Stop if marked
if (visitedNodes[node]) {
return;
}

// Marked
visitedNodes[node] = true;

// Visit each child
for (int child = 1; child < visitedNodes.length; child++) {
if (graph[node][child]) {
visit(child, visitedNodes, speakerList, graph);
}
}

speakerList.insert(0, node + " ");
speakerCount++;
}

Edited by author 23.05.2014 15:48
Re: What's wrong with my Topological Sorting?
Posted by martin_2435 7 Jan 2015 04:09
I think the problem is that a children could have more than 1 parent - and here you have to check if all of his parents have been printed. If you can't find the solution yourself - write and I will tell you a way.

P.S. Other people say that "One of the lines in test 4 has trailing space. This old problem was designed for Pascal/C++, such inputs treated as a bad style nowadays."
I don't know what this means, but first check if this is the problem!

Edited by author 07.01.2015 04:12