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

Обсуждение задачи 1128. Деление на группы

WA#8, help me
Послано Филиппов Илья (УЛ) 1 май 2008 02:18
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,i,j,p,x;
vector<int> a[10000];
vector<int> b,c;
int d[10000];

void dfs(int i,int k)
{
    d[i] = 1;
    int j;
    for (j = 0;j<a[i].size();j++)
        if (d[a[i][j]] == 0)
    {
        if (k == 1)
        {
            c.push_back(a[i][j]);
            dfs(a[i][j],0);
        }
        else
        {
            b.push_back(a[i][j]);
            dfs(a[i][j],1);
        }
    }
}

int main()
{
    cin >> n;
    for (i = 1;i<=n;i++)
    {
        cin >> p;
        for (j = 1;j<=p;j++)
        {
            cin >> x;
            a[i].push_back(x);
        }
    }
    for (i = 1;i<=n;i++)
        if (d[i] == 0)
        {
            b.push_back(i);
            dfs(i,1);
        }
    if (b.size()<=c.size())
    {
        cout << b.size() << endl;
        if (b.size()>0)
        for (i = 0;i<b.size();i++)
            cout << b[i] << " ";
    }
    else
    {
        cout << c.size() << endl;
        if (c.size()>0)
        for (i = 0;i<c.size();i++)
            cout << c[i] << " ";
    }
    return 0;
}
Re: WA#8, help me
Послано Proba 11 ноя 2010 00:22
6
3 2 3 4
2 1 3
3 1 2 5
3 1 5 6
3 3 4 6
2 4 5