0 / 0 / 1
Регистрация: 07.12.2015
Сообщений: 33
1

Теория графов. Задача Обрати меня!

27.01.2016, 12:05. Показов 5094. Ответов 3
Метки нет (Все метки)

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

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

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

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

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

1 4
1 2
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.01.2016, 12:05
Ответы с готовыми решениями:

Теория графов
Есть задание. найти максимальное и среднее расстояние между центральными вершинами...

Построение. Теория графов
Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало...

Алгоритм Флойда (теория графов)
код: int** floid(int** W,int n){ vector<int**>D(n); int** A=new int*; for(int i=0;i<n;i++){...

Теория графов. Найти время
Здравствуйте. Новичок. Впервые столкнулся с графами. Есть вот такая задача: "По завершению турнира...

3
Dimension
591 / 459 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
27.01.2016, 12:22 2
это же базовая задача ,почему сами не хотите сделать?
0
93 / 69 / 22
Регистрация: 17.10.2011
Сообщений: 235
27.01.2016, 12:26 3
Теория графов. Задача Обрати меня!

35 строчек, чувак просит написать ему решение, чтоб не делать задание на сайте для самообучения
0
0 / 0 / 0
Регистрация: 05.11.2021
Сообщений: 3
03.01.2022, 21:06 4
Такс. Я сделал решение довольно замороченным, но не важно))) Решение сделано с опорой на пройденный материал "структуры данных". А так, там решение в 35 строк))))


C++
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <sstream>
#include <fstream>
 
using namespace std;
 
class steck
{
public:
    steck();
    void push_back(int data);
    int pop_front();
    int get_size() { return Size; };
 
private:
 
    class Node
    {
    public:
        Node* pNext;
        int data;
        Node(int data = int(), Node* pNext = nullptr)
        {
            this->data = data;
            this->pNext = pNext;
        }
    };
    Node* head;
    int Size;
    Node* back;
};
 
steck::steck()
{
    Size = 0;
    head = nullptr;
}
 
void steck::push_back(int data)
{
    if (head == nullptr)
    {
        head = new Node(data);
        back = head;
    }
    else
    {
        back->pNext = new Node(data);
        back = back->pNext;
    }
    Size++;
}
 
int steck::pop_front()
{
    Node* current = head;
    int item = current->data;
    head = head->pNext;
    delete current;
    Size--;
    return item;
}
 
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int n;
    fin >> n;
    steck* matr = new steck[n];
 
 
 
    string str;
    getline(fin, str);
    for (int i = 0; i < n; i++)
    {
        getline(fin, str);
        stringstream ss;
        ss << str + " ";
        //cout << str << endl;
        int elem = 0;
        for (; ss >> elem;)
        {
            //cout << elem << endl;
            matr[elem - 1].push_back(i + 1);
        }
    }
 
    fout << n << endl;
    //cout << n << endl;
 
    for (int i = 0; i < n; i++)
    {
        int len = matr[i].get_size();
        for (int j = 0; j < len; j++)
        {
            int s = matr[i].pop_front();
            fout << s << " ";
            //cout << s << " ";
        }
        //cout << endl;
        fout << endl;
    }
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.01.2022, 21:06
Помогаю со студенческими работами здесь

Теория графов и мат логики( си и си++)
Указания к выполнению лабораторной работы 1. Упорядочить заданные вариантом множества. Для...

Интересная задача, теория графов
Здравствуйте. Имеется следующая задача задача: (в приложении) Суть задачи мне вроде бы ясна....

Теория графов
Здравствуйте! Подскажите плз, с чего начать. Доказать, что граф, в котором существуют две...

Теория графов
Выписать все образующие циклической группы &lt; а&gt; порядка 12 Весь семестр отдыхал, а теперь вот...:(...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru