Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
zeppus
 Аватар для zeppus
1 / 1 / 0
Регистрация: 07.02.2010
Сообщений: 64
24.04.2014, 21:00     Нахождение стоков и истоков в графе по матрице смежности #1
Доброго времени суток, Гуру). Решаю задачки из 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 минут
Так как задача вроде бы решена. Посоветуйте пожалуйста еще ресурсы со всякими интересными (олимпиадными) задачками.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2014, 21:00     Нахождение стоков и истоков в графе по матрице смежности
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru