Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
zeppus
1 / 1 / 0
Регистрация: 07.02.2010
Сообщений: 64
#1

Нахождение стоков и истоков в графе по матрице смежности - C++

24.04.2014, 21:00. Просмотров 1888. Ответов 0
Метки нет (Все метки)

Доброго времени суток, Гуру). Решаю задачки из http://informatics.mccme.ru/moodle/ проблема в том, что я не могу сдать следующую задачу:
Напомним, что вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.
Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.
Формат входных данных:
Сначала вводится число n – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Формат выходных данных:
В первой строке выведите k – число истоков в графе и затем k чисел – номера вершин, которые являются истоками, в возрастающем порядке. Во второй строке выведите информацию о стоках в том же порядке.
Пример
Входные данные
4
1 0 0 1
0 0 0 0
1 1 0 1
0 0 0 0
Выходные данные
1 3
2 2 4
Программа проходит только 3 теста.
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
#include <fstream>
int main() {
    using namespace std;
    ifstream in("input.txt");
    ofstream out("output.txt");
    int n;
    in >> n;
    int **a = new int*[n];
    for (int i = 0; i < n; i++) {
        a[i] = new int[n];
        for (int j = 0; j < n; j++)
            in >> a[i][j];
    }
    int *src = new int[n]; for (int i = 0; i < n; i++) src[i] = 0;
    int *des = new int[n]; for (int i = 0; i < n; i++) des[i] = 0;
    int csrc = 0, cdes = 0;
    int f1, f2;
    for (int i = 0; i < n; i++) {
        f1 = f2 = 0;
        for (int j = 0; j < n; j++) f1 += a[i][j];
        for (int di = 0; di < n; di++) f2 += a[di][i];
        if ((f1 != 0) && (f2 == 0)) {
            csrc++;
            src[i] = i + 1;
        } else if ((f1 == 0) && (f2 != 0)) {
            cdes++;
            des[i] = i + 1;
        }
    }
    out << csrc;
    for (int i = 0; i < n; i++)
        if (src[i] != 0) out << ' ' << src[i];
    out << endl << cdes;
    for (int i = 0; i < n; i++)
        if (des[i] != 0) out << ' ' << des[i];
    in.close();
    out.close();
    for (int i = 0; i < n; i++)
        delete [] a[i];
    delete [] a;
    return 0;
}
Проверил задачу на нескольких примерах (самодельных) - все верно. Помогите, пожалуйста, найти ошибку!
Спасибо.

Добавлено через 50 секунд
ссылка на задачу http://informatics.mccme.ru/mod/stat...&chapterid=474

Добавлено через 15 минут
Wow, прошла!!! Всем спасибо)))
вот код:
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
#include <fstream>
int main() {
    using namespace std;
    ifstream in("input.txt");
    ofstream out("output.txt");
    int n;
    in >> n;
    int **a = new int*[n];
    for (int i = 0; i < n; i++) {
        a[i] = new int[n];
        for (int j = 0; j < n; j++)
            in >> a[i][j];
    }
    int *src = new int[n]; for (int i = 0; i < n; i++) src[i] = 0;
    int *des = new int[n]; for (int i = 0; i < n; i++) des[i] = 0;
    int csrc = 0, cdes = 0;
    int f1, f2;
    for (int i = 0; i < n; i++) {
        f1 = f2 = 0;
        for (int j = 0; j < n; j++) // sum of line
            f1 += a[i][j];
        for (int j = 0; j < n; j++)
            f2 += a[j][i];
        if (f1 == 0) {
            cdes++;
            des[i] = i + 1;
        }
        if (f2 == 0) {
            csrc++;
            src[i] = i + 1;
        }
    }
    out << csrc;
    for (int i = 0; i < n; i++)
        if (src[i] != 0) out << ' ' << src[i];
    out << endl << cdes;
    for (int i = 0; i < n; i++)
        if (des[i] != 0) out << ' ' << des[i];
    in.close();
    out.close();
    for (int i = 0; i < n; i++)
        delete [] a[i];
    delete [] a;
    return 0;
}
все оказалось несколько проще...

Добавлено через 2 минуты
Хотя при такой проверке несвязные вершины будут "добавляться" и туда и сюда (и в стоки и истоки) ИМХО.

Добавлено через 6 минут
Так как задача вроде бы решена. Посоветуйте пожалуйста еще ресурсы со всякими интересными (олимпиадными) задачками.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2014, 21:00
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Нахождение стоков и истоков в графе по матрице смежности (C++):

Реализация матрицы смежности и инцидентности, поиск циклов в графе - C++
Здравствуйте. Есть программа, выводящая матрицу смежности и инцидентности. Прошу помощи в реализации добавления и удаления вершин и рёбер...

Определить планарность графа по матрице смежности - C++
в общем есть файлы с матрицами смежностей, формат файла прикладыва. (graph1.txt , graph2.txt) В первой строчке указывается количество...

По матрице инцидентности построить матрицу смежности - C++
Здравствуйте, помогите пожалуйста с заданием: По матрице инцидентности графа G построить матрицу смежности, если 1) G — простой...

Нахождение мостов в графе. - C++
Дан граф.Найти все мосты.Мост-ребро при удалении которого создается компонента связности(проще говоря если удалить такое ребро,то...

Определение матрицы смежности графа по заданной матрице инцидентности - C++
Доброй ночи :) Изучаю графы, написал фукнцию для конвертации матрицы инцидентности в матрицу смежности, а наоборот не выходит. ...

Вывести все возможные комбинации цепочек в матрице смежности - C++
Есть матрица смежности вида: AB0 BCD DD0 CKN NE0 KB0 Т.е. если в конце строки 0, то из одного узла есть связь только к одному...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2014, 21:00
Привет! Вот еще темы с ответами:

Нахождение циклов в графе , используя смежную матрицу - C++
Возникла такая задача: используя смежную матрицу, нужно определить циклы графа. Граф ненаправленный и нет мультивекторов(т.е. наша матрица...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...

Нахождение всех путей в графе от одной вершины до другой обходом в ширину - C++
Здравствуйте, уважаемые любители и профессионалы программирования. Нужна мне помощь в такой задаче. Необходимо найти для любого...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru