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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Метод Йордана-Гаусса. Как изменяется обратная матрица в силу таких преобразований? http://www.cyberforum.ru/cpp-beginners/thread1156556.html
Выше описанным методом требуется найти определитель. Ведущий элемент выбирается максимальный . (Те максимальный элемент перебирается в левый верхний угол) как изменяется обратная матрица в силу таких преобразований ?(переестановки строк и столбцов) Добавлено через 6 минут Оооой определитель говорю обратную матрицу
C++ Работа с сетью, работа с БД и парсинг информации. Разделение потоков Возникла проблема разграничения потоков. То есть в конечном файле реализованы алгоритмы: работа с сетью, работа с БД и парсинг информации. Преподаватель сказал, что категорически запрещается, чтобы всё это работало в одном потоке. Необходимо сделать в разных. Помогите, пожалуйста кто чем сможет, очень срочно, до субботы(26.04) нужно сделать. Это код главного файла MainWindow: #include... http://www.cyberforum.ru/cpp-beginners/thread1156555.html
C++ Вывести слова, в которых нет повторяющихся букв
Вариант 8. Вывести слова, в которых нет повторяющихся букв. Вывести слова, в которых буквы упорядочены по алфавиту. выкидываю все, что есть(только функция на проверку повтора-в ней проблема),помогите,но обязательно используя объекты класса «String» #include "stdafx.h" int kol_slov(string& s, int& kol); void fun(string* s2, string& s, int kol);
Функции. Найти строку матрицы у которой все элементы делятся на 3 C++
Имеем целочисленную матрицу n x n, найти строку все элементы которой длятся на 3 нацело.
C++ Сортировка текста по алфавиту http://www.cyberforum.ru/cpp-beginners/thread1156539.html
Cоздать програму, какая имеет некоторый текст и выводит его в алфавитном порядке, начальную строку ввести в главной программе.
C++ Дана матрица размера 6x9. Поменять местами строки содержащие минимальный и максимальный элемент дана матрица размера 6x9 поменять местами строки содержащие минимальный и максимальный элемент (такие элементы должны быть одни) ))) спасибо заранее!! подробнее

Показать сообщение отдельно
zeppus
 Аватар для zeppus
1 / 1 / 0
Регистрация: 07.02.2010
Сообщений: 64
24.04.2014, 21:00     Нахождение стоков и истоков в графе по матрице смежности
Доброго времени суток, Гуру). Решаю задачки из 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 минут
Так как задача вроде бы решена. Посоветуйте пожалуйста еще ресурсы со всякими интересными (олимпиадными) задачками.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 12:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru