Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.88/50: Рейтинг темы: голосов - 50, средняя оценка - 4.88
0 / 0 / 0
Регистрация: 07.04.2019
Сообщений: 69

Развернутый граф

12.12.2019, 23:01. Показов 9752. Ответов 3

Студворк — интернет-сервис помощи студентам
Добрый день, есть такая задача:


Мальчик Вася очень любит разворачивать ориентированные графы. Помогите ему в этом.

Входные данные
Во входном файле записано число N (1 ≤ N ≤ 50000) - количество вершин в графе. В следующих N строках записан граф в виде списков смежности: в i-ой строке, в порядке возрастания, записаны номера вершин, в которые идут ребра из i-ой вершины. Нумерация начинается с единицы. Гарантируется, что ребер в графе не более 50000.

Выходные данные
Выведите развернутый граф в том же формате, что и исходный.

Примеры
входные данные
4
2 3
3

2
выходные данные
4

1 4
1 2


Я написал код, но проверяющая система ставит в некоторых тестах "Ошибку во время выполнения программы" (не тайм-лимит)
Что может быть не так? (Звездочками я помечаю вершины в которых уже был)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
n = int(input())
arr = []
k = 0
graph = [[0] * n for i in range(n)]
for i in range(n):
    for j in list(map(int, input().split())):
        graph[i][j - 1] = 1
#for k in graph:
    #print(' '.join(map(str, k)))
 
for i in range(n):
    for j in range(n):
        if '*' not in str(graph[i][j]) and '*' not in str(graph[j][i]):
            graph[i][j], graph[j][i] = graph[j][i], graph[i][j]
            graph[i][j] = str(graph[i][j]) + '*'
            graph[j][i] = str(graph[j][i]) + '*'
#print('-------------------')
for i in range(n):
    for j in range(n):
        if '*' in graph[i][j]:
            graph[i][j] = str(graph[i][j]).replace('*', '')
        if '**' in graph[i][j]:
            graph[i][j] = str(graph[i][j]).replace('**', '')
for i in range(n):
    for j in range(n):
        graph[i][j] = int(graph[i][j])
#for k in graph:
    #print(' '.join(map(str, k)))
#print('----------------')
print(n)
for k in graph:
    if len(set(k)) == 1 and 0 in k:
        print('')
        continue
    else:
        for j in range(len(k)):
            if k[j] == 1:
                arr.append(j + 1)
        arr.sort()
        print(*arr)
        arr.clear()
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
12.12.2019, 23:01
Ответы с готовыми решениями:

Реализовать граф от 1 до 10: граф связный; -число от 1 до 10, могут повторяться
Реализовать граф от 1 до 10: граф связный; -число от 1 до 10, могут повторяться. Добавить рандом W (y) = random {i = 1, n-1; j = 2;...

Ориентированный развернутый граф
Помогите пожалуйста!! Не могу понять как это ориентированный развернутый граф!! Объясните пожалуйста!!))

Развернутый текст
всем привет! всех с наступившим. нужно сделать такое. подскажите в каком напровлении мне информацию поискать.

3
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
12.01.2023, 23:04
читай про поиск в ширину, алгоритм Дейкстры.

Не по теме:

почему Ц-шники у нас в разделе питона?

1
Эксперт Python
 Аватар для Red white socks
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
13.01.2023, 11:02
Цитата Сообщение от alilxxey Посмотреть сообщение
читай про поиск в ширину, алгоритм Дейкстры.
это точно будет не во вред)
Но здесь просто ориентацию ребер надо поменять)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import defaultdict
 
n = int(input())
graph = {}
for i in range(n):
    graph[i+1] = list(map(int,input().split()))
    
reverse_graph = defaultdict(list)
for vert,edges in graph.items():
    for e in edges:
        reverse_graph[e].append(vert)
        
print(n)
for i in range(n):
    print(*sorted(reverse_graph[i+1]))
Добавлено через 5 минут
Ох, ёлки, да вы alilxxey - некромант)
1
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
13.01.2023, 15:05
Red white socks,
Цитата Сообщение от Red white socks Посмотреть сообщение
Ох, ёлки, да вы alilxxey - некромант)


это не я!!! тут просто был пост (видимо сейчас удален), где закинули код на плюсах. поэтому и написал про цшников
Цитата Сообщение от alilxxey Посмотреть сообщение
почему Ц-шники у нас в разделе питона?
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
13.01.2023, 15:05
Помогаю со студенческими работами здесь

Развернутый вид IE
Win XP При переходе по ссылке из Офиса IE открывается в маленьком окошке, что не удобно. Пытался прозондировать вопрос. Выполнял...

Развернутый связный список
Для реализации развернутого связного списка какой размер массива подойдет лучше: 8 или 16? При 16 будет в два раза меньше самих узлов, чем...

Нарисовать развернутый кубик
сделать блок схему и программу ...или только программу

Развернутый бином Ньютона
Доброго всем времени суток! В общем проблемка у меня возникла такая: Для чисел k & n, которые вводит пользователь, необходимо...

Требуется развернутый материал по редактору реестра
Существуют ли в природе книги или мануалы или FAQ с подробнейшим описанием реестра и всех его разделов подразделов у Windows 10 & 7 ?...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru