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

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

What's wrong with my Topological Sorting?
Послано Peter P 23 май 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?
Послано martin_2435 7 янв 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