Discussion @ 1022. Genealogical Tree @ Timus Online Judge

Khujamurod Can you explain this test? [10] // Problem 1022. Genealogical Tree 14 Jul 2017 12:26

Help! I dont understand that problem.
test:
3
0
1 0
0
can you explain which one is right ?
2 1 3
or
3 2 1

Khujamurod Re: Can you explain this test? [6] // Problem 1022. Genealogical Tree 14 Jul 2017 12:27

In addition I get WA6 and this is my code :
/*
#include <stdio.h>
#define maxn 105

int vp[maxn], pv[maxn];

int main() {

    int n, x, y;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        vp[i] = i;
        pv[i] = i;
    }
    for (int i = 1; i <= n; i ++) {
        int min = vp[i];
        while(1) {
            scanf("%d", &x);
            if(x == 0) break;
            if(vp[x] < min) min = vp[x];
        }
        for (int j = i - 1; j >= min; j --) {
            pv[j + 1] = pv[j];
            vp[pv[j + 1]] = j + 1;
        }
        pv[min] = i;
        vp[i] = min;
    }
    for (int i = 1; i <= n; i ++) {
        printf("%d ", pv[i]);
    }
    return 0;
}
*/

Mahilewets Re: Can you explain this test? [4] // Problem 1022. Genealogical Tree 14 Jul 2017 12:42

I don't understand what your code does.
Probably intended solution uses an algorithm calling "topological sorting". (My solution uses it too).
By definition, topological sorting solves the task 1022.

Khujamurod Re: Can you explain this test? // Problem 1022. Genealogical Tree 14 Jul 2017 12:44

Edited by author 14.07.2017 12:44

Khujamurod Re: Can you explain this test? [1] // Problem 1022. Genealogical Tree 14 Jul 2017 12:44

Yeah you are right. It is not an algorithm. It is just an idea but i think this idea should accept!

Mahilewets Re: Can you explain this test? // Problem 1022. Genealogical Tree 14 Jul 2017 13:34

Yes, I made a mistake.
Correct would be something like.

Intended solution is a program that calculates topological sort of vertices of a graph built from input data using some well-known algorithm for calculating topological sorting

Mahilewets Re: Can you explain this test? // Problem 1022. Genealogical Tree 14 Jul 2017 12:45

In topological sorting, you are doing depth first search and memorize vertices when you leave them.
When all the vertices are considered, you have memorized vertices in reversed topological sorted order.

Edited by author 14.07.2017 12:45

Husayn Hasanov Re: Can you explain this test? // Problem 1022. Genealogical Tree 19 Sep 2017 16:00

void dfs(int nd)
{
    for(int to : adj[nd])
        if(!used[to])
            dfs(to);
    used[nd] = true;    //switch the node into visited
    ans.push_back(nd); //put the node to array
}

Edited by author 19.09.2017 16:03

Mahilewets Re: Can you explain this test? // Problem 1022. Genealogical Tree 14 Jul 2017 12:39

My AC program gives "3 2 1".
So, probably "3 2 1" is the right answer.

Husayn Hasanov Re: Can you explain this test? [1] // Problem 1022. Genealogical Tree 19 Sep 2017 15:55

If several sequences satisfy the conditions of the problem, you are to write to the standard output any of them!!! ;) ;/

Husayn Hasanov Re: Can you explain this test? // Problem 1022. Genealogical Tree 19 Sep 2017 15:59

You should all do just DFS!(How? Just enter any node and check its adjacents were visited. So that enter node which was not visited before. Finally, put this node to array after checking and reverse the answer array)!

Edited by author 19.09.2017 16:04

Discussion of Problem 1022. Genealogical Tree