Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Матрица смежности неориентированного графа / 16 сообщений из 16, страница 1 из 1
08.03.2015, 14:37
    #38898394
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
Простой неоринтированный граф задан списком ребер.Выедите его представление в виде матрицы смежности.На вход дают Число Н-кол-во вершин графа и М- кол-во ребер,далее следует М строк по 2 числа в каждой-список ребер графа.Надо вывести матрицу смежности.
Организовал я это на си++ таким образом,считываю ребра в дувмерный массив ,потом присваеваю элемент двумерного массива единице с номером ребра которое дано было на ввод и вывожу матрицу смежности,собственно вот сам код:
Код: plaintext
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.
#include <iostream>
#include <stdio.h>


using namespace std;

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	bool a[100][100]={0};
	int  v[100][100];
	int i, j, n,m, count = 0;
	cin >> n>>m;
	int k = 0;
	for (int i = 0; i<m; ++i)
	{
		for (int j = 0; j<2; ++j)
		{
			cin >> v[i][j];
			if (j==1)
			{
			int aa=v[i][j]-1,aa1=v[i][j-1]-1;
            a[aa1][aa]=1;
			a[aa][aa1]=1;
			}
		}
		
	}
	for (int i = 0; i<n; ++i)
	{
		for (int j = 0; j<n; ++j)
		{
			
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}

	return 0;
}


Хотел бы у вас узнать что в нем не так ибо в системе проверки заходит лишь на пол балла ,на 50 из 100.
...
Рейтинг: 0 / 0
10.03.2015, 02:28
    #38899305
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
ванмомас намбаван,

зачем вы объявляется i,j в самом начале ?
Код: plaintext
1.
int i, j, n,m, count = 0;



Почему массив неориентированного графа 100x100? (вы используете в 50 раз меньше) И почему вы не прокомментировали где и что ? Я вам уже давно писал, вы просите помощи у С/С++ программистов, а не у дворников. Потрудитесь уважать тех, кто читает ваш код(хотя и дворников нужно уважать).

ваше условие в двойном цикле не нужно(см. ниже рефакторинг)
Код: plaintext
1.
if (j==1)



не уверен что у вас корректная работа с n,m.
также, вы не вызвали fclose()

рефакторинг в самом первом приближении

Код: plaintext
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.
#include <iostream>
#include <stdio.h>


using namespace std;

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	bool a[100][100] = { 0 };//матрица смежности
	int  v[100][2];//неориентированный граф
	int n, m, count = 0;
	cin >> n >> m;
	int k = 0;
	for (int i = 0; i<m; ++i)
	{
		for (int j = 0; j < 2; ++j){
			cin >> v[i][j];
		}
		int aa = v[i][1] - 1, aa1 = v[i][0] - 1;
		a[aa1][aa] = 1;
		a[aa][aa1] = 1;

	}

	for (int i = 0; i<n; ++i){
		for (int j = 0; j<n; ++j){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}



И что у вас за ужаснейшее именование aa, aa1 ?что дальше, aaa1 ?
...
Рейтинг: 0 / 0
10.03.2015, 09:32
    #38899433
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
ванмомас намбаван,
Вы пишете на С? Тогда зачем вам cin и cout?
на С++? Тогда откуда достали stdin и stdout?
Что за паскалевская привычка объявлять все переменные в начале блока? (ладно-ладно, _старый_ С тоже требовал это...)

Вы задаёте матрицу фиксированного размера. Что будет, если на вход подадут граф бОльшей размерности? Что интересно, сам размер вы хоть и читаете, но даже не проверяете...
...
Рейтинг: 0 / 0
10.03.2015, 09:34
    #38899438
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
И не злоупотребляйте оператором "," запятая. Не экономьте перевод каретки.
...
Рейтинг: 0 / 0
11.03.2015, 22:00
    #38901891
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
BagaBaga,я знаю какой размерности массив будет введен
...
Рейтинг: 0 / 0
14.03.2015, 11:47
    #38904817
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
BagaBaga,а почему нельзя юзать cin & cout?
...
Рейтинг: 0 / 0
16.03.2015, 09:03
    #38905500
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
ванмомас намбаван,
cin и cout использовать, конечно же, можно. А вот смешивать ввод-вывод в стиле С (stdin, stdout) и C++ (cin, cout) не рекомендуется - черевато разными багами. Причём, неожиданными и плохо воспроизводимыми.
...
Рейтинг: 0 / 0
16.03.2015, 09:05
    #38905503
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
ванмомас намбаванBagaBaga,я знаю какой размерности массив будет введен
Тогда зачем вы эту самую размерность упорно читаете? ... если всё знаете ещё до компиляции.
ванмомас намбаван...
Код: plaintext
1.
2.
3.
...
	cin >> n>>m;
...
...
Рейтинг: 0 / 0
17.03.2015, 00:01
    #38906498
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
Так понимаю,
эту задачу - http://informatics.mccme.ru/mod/statements/view3.php?id=359&chapterid=465
пытаетесь решить?
...
Рейтинг: 0 / 0
17.03.2015, 20:44
    #38907558
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
Раз ТС больше интереса не проявляет, думаю, большого вреда от публикации (какого-то) решения - не будет. Решает задачу для условий из http://informatics.mccme.ru/mod/statements/view3.php?id=359&chapterid=465 , кроме одного: данные читаем со стандартного потока ввода, пишем на стандартный поток вывода.

Код: plaintext
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.
 #include <iostream>

    //глобальные массивы - зло. Но в этом случае - самое оно.
    int adj_mtx[100][100];

    using namespace std;

    int main()
    {
        int num_edj    = 0;
        int num_vertex = 0;

        cin >> num_vertex
             >> num_edj;

        //рёбра обрабатываем по одному, num_edj штук. И сразу - в матрицу
        while(num_edj--){
            register int start;
            register int stop;

            cin >> start
                 >> stop;

            //пришлось использовать '--', ведь у нас по задаче
            //нумерация с 1, а индексы в массивах - с нуля...
            adj_mtx[--start][--stop] = 1;
            adj_mtx[stop][start]     = 1;
        }

        //вывод матрицы. Ваш КЭП.
        for(int i = 0; i < num_vertex; i++){
            for(int j = 0; j < num_vertex; j++){
                cout << adj_mtx[i][j] << ' ';
            }
            cout << endl;
        }
        // надеюсь, ошибок ввода-вывода не было - я их не обрабатывал.
        // Но для демки именно преобразования списка рёбер в матрицу смежности - сойдёт.
        return 0;
    }
...
Рейтинг: 0 / 0
18.03.2015, 13:09
    #38908263
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
BagaBaga
Код: plaintext
1.
register int start;

ишь ты, регистер, кто то им ещё пользуется ))
...
Рейтинг: 0 / 0
18.03.2015, 17:26
    #38908845
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
egorychBagaBaga
Код: plaintext
1.
register int start;

ишь ты, регистер, кто то им ещё пользуется ))
Ну бывает. Тем более, в этом случае компилятор всё равно её скорее всего проигнорирует..
...
Рейтинг: 0 / 0
22.03.2015, 15:11
    #38912433
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
BagaBaga,я на форум давно не заходил прост,занят Objective-C.А задачу там решил.Прост не правильно была задана размерность массива.А что такое register?
...
Рейтинг: 0 / 0
23.03.2015, 20:12
    #38914073
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
ванмомас намбаванА задачу там решил.Прост не правильно была задана размерность массива.
Так понимаю, с размерностью массива под хранение рёбер ошибся. Должен был [макс. число рёбер = n*(n-1)][число вершин в ребре = 2]. Правда, я всё равно не понимаю, зачем их хранить - только память впустую тратить...

ванмомас намбаванА что такое register?
Подсказка компилятора, что эту переменную следует разместить в регистре, а не памяти. Правда, компилятор имеет полное право проигнорировать эту подсказку. И в этом коде почти наверняка так и сделает - из-за передачи переменной в функцию cin.operator>>(int). Вот и получается, что эта подсказка как бы лишняя - компилятор может положить на неё, а прогер будет "наивно" думать о ней как о регистровой...
...
Рейтинг: 0 / 0
23.03.2015, 20:15
    #38914077
BagaBaga
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
register
Хм, он ещё и deprecated оказался...
...
Рейтинг: 0 / 0
23.03.2015, 21:55
    #38914161
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Матрица смежности неориентированного графа
BagaBagaон ещё и deprecated оказался...я потому и удивился, когда его увидел ))
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Матрица смежности неориентированного графа / 16 сообщений из 16, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]