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?

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*