Тема: Задача Корупція
Хто може кинути розв'язок або сказати як зробити дану задачу?
http://acm.timus.ru/problem.aspx?space=1&num=1198
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Задача Корупція
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Хто може кинути розв'язок або сказати як зробити дану задачу?
http://acm.timus.ru/problem.aspx?space=1&num=1198
Для кожного сенатора визначіть список сенаторві на яких він має вплив (як прямо так і не прямо через тих на яких прямо), і ті сенатори в яких цей список включатиме всіх - наймогутніші
П.С. Якщо не секрет, нащо вам то?
Просто будуєте зв'язаний граф для кожного сенатора.
.
Якраз розглядали дану задачу на факультативі і пан koala все вірно підказав.
Якраз розглядали дану задачу на факультативі і пан koala все вірно підказав.
а є код з факультативу?)
Хапайте Python:
n = int(input())
data = [set()]+[set(int(x) for x in input().split()) for _ in range(n)]
print(data)
def infl(num,data,visited):
visited.add(num)
res = data[num].copy()
for x in data[num]:
if x not in visited:
res |= infl(x,data,visited)
data[num] = res
return data[num]
for x in range(len(data)):
infl(x,data,set())
print([x for x in range(n) if len(data[x])>n])
Вдався до маленьких хитрощів - наприклад, додав віртуального "сенатора №0", щоб не змінювати номери в масиві.
Ефективніша ідея: робимо матрицю суміжності (можна бітову) і в циклі по рядках робимо АБО з тими рядками, з якими у відповідних клітинках стоять одиниці, доки не буде n проходів без змін.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися