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

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

saba program [1] // Задача 1022. Генеалогическое дерево 2 июн 2007 20:00
I want c++ program which gives AC

Edited by author 02.06.2007 20:02
timur Re: program // Задача 1022. Генеалогическое дерево 14 авг 2007 09:55
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int i, k, n;
    cin >> n;
    vector< set<int> > out(n), in(n);
    for (i=0;i<n;i++) while (cin>>k, k) { out[i].insert(--k); in[k].insert(i); }
    set<int> q;
    for (i=0;i<n;i++) if (in[i].empty()) q.insert(i);
    vector<int> top;
    while (!q.empty()) {
        top.push_back(k=*q.begin());
        q.erase(q.begin());
        for (set<int>::iterator it=out[k].begin();it!=out[k].end();++it) {
            i=*it;
            in[i].erase(k);
            if (in[i].empty()) q.insert(i);
        }
    }
    cout << top[0]+1; for (i=1;i<n;i++) cout << ' ' << top[i]+1;
    return 0;
}