e-olymp 5082. Степени вершин

19/04/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp.

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

Входные данные

В первой строчке находится число [latex]1 \leq N \leq 1000[/latex] В следующих [latex]N[/latex] строчках находится матрица смежности.

Выходные данные

Выведите [latex]N[/latex] чисел – степени всех вершин.

Тесты

Ввод	Вывод
2 0 1 1 0	1 1
3 0 1 0 1 0 1 0 1 0	1 2 1
3 0 1 0 1 0 1 0 1 0	1 4 1
5 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1	6 1 6 1 6
5 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1	1 3 4 3 3
5 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0	4 1 4 1 4
5 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0	3 3 2 1 1

Алгоритм

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия [latex]N[/latex] раз, для каждой строки матрицы. Храним ответ в переменной counter, изначально [latex]0[/latex]. По очереди считываем все ее элементы и, если текущий элемент равен [latex]1[/latex], то прибавялем степени [latex]2[/latex], если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — [latex]1[/latex]. Затем выводим результат через пробел.

Код

#include <iostream>
using namespace std;

int main() 
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int counter = 0, x;
		for (int j = 0; j < n; j++)
		{
			cin >> x;
			if (x)
				counter += (i == j ? 2 : 1);
		}
		cout << counter << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

ios::sync_with_stdio(false);

int n;

cin >> n;

for (int i = 0; i < n; i++)

{

int counter = 0, x;

for (int j = 0; j < n; j++)

{

cin >> x;

if (x)

counter += (i == j ? 2 : 1);

}

cout << counter << " ";

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.
Код для тестирования на Ideone.

Related Images:

e-olimp 5074. Степени вершин по спискам ребер

02/05/2015 by Карташов Денис Геннадійович

Задача:

Неориентированный граф задан списком ребер.

Найдите степени всех вершин графа.

Технические условия:

Входные данные:

Входной файл содержит числа [latex]n[/latex] [latex] (1 \leq n \leq 100) [/latex] — число вершин в графе и

[latex]m[/latex] [latex](1 \leq m \leq \frac{n(n-1)}{2})[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

Выходные данные:

Выведите в выходной файл [latex]n[/latex] чисел — степени вершин графа.

Результат на C++

Результат на Java

Код на C++:

#include <iostream>
using namespace std;

int main() {
   int n = 0 , m = 0, i, buf;
   cin >> n >> m;
   int *a = new int [n];
   for(i = 0; i < n; a[i] = 0, ++i);
   for(i = 0 , buf; i < 2*m ; cin >> buf, ++a[buf - 1], ++i);
   for(i = 0; i < n; ++i){
   		 cout << a[i] << endl;
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n = 0 , m = 0, i, buf;

cin >> n >> m;

int *a = new int [n];

for(i = 0; i < n; a[i] = 0, ++i);

for(i = 0 , buf; i < 2*m ; cin >> buf, ++a[buf - 1], ++i);

for(i = 0; i < n; ++i){

cout << a[i] << endl;

}

return 0;

}

Код на Java:

import java.io.*;
import java.util.*;

public class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n, m, i, buf;
		n = in.nextInt();
		m = in.nextInt();
		int[] a = new int [n];
		for(i = 0; i < n; a[i] = 0, ++i);
		for(i = 0; i < 2*m ;buf = in.nextInt(), ++a[buf - 1], ++i);
		for(i = 0; i < n; ++i){
			out.println(a[i]);
		}
		out.flush();
	}
}

import java.io.*;

import java.util.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n, m, i, buf;

n = in.nextInt();

m = in.nextInt();

int[] a = new int [n];

for(i = 0; i < n; a[i] = 0, ++i);

for(i = 0; i < 2*m ;buf = in.nextInt(), ++a[buf - 1], ++i);

for(i = 0; i < n; ++i){

out.println(a[i]);

}

out.flush();

}

Описание:

Мне дан неориентированный граф, значит каждое упоминание вершины в списке ребер увеличивает её степень на единицу. Заводим массив (размер массива равен числу вершин) и при каждом упоминании вершины увеличиваем её ячейку в массиве на единицу. Выводим результат.

Related Images:

e-olimp 5080. Количество висячих вершин 1

29/04/2015 by Марченко Філіп Олександрович

Код:

#include <iostream>
#include <vector>
using namespace std;

int gr[1001][1001]; // матрица смежности
int n; //кол-во вершин
	
//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во
//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.
//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице 
//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int ans = 0; //предположим, что граф не имеет висячих вершин 
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> gr[i][j];	//ввод матрицы смежности
	for (int i=0; i<n; i++){
		int cnt = 0; //счётчик
		for (int j=0; j<n; j++){
			if (gr[i][j] == 1) cnt++;  //подсчёт степени
		}
		if (cnt==1) ans++;  //проверка на висячую вершину
	}
	cout << ans << endl;	//вывод ответа
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int gr[1001][1001]; // матрица смежности

int n; //кол-во вершин

//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во

//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.

//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице

//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {

ios::sync_with_stdio(false);

cin >> n;

int ans = 0; //предположим, что граф не имеет висячих вершин

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

cin >> gr[i][j]; //ввод матрицы смежности

for (int i=0; i<n; i++){

int cnt = 0; //счётчик

for (int j=0; j<n; j++){

if (gr[i][j] == 1) cnt++; //подсчёт степени

}

if (cnt==1) ans++; //проверка на висячую вершину

}

cout << ans << endl; //вывод ответа

return 0;

}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: степень вершины

e-olymp 5082. Степени вершин

Related Images:

e-olimp 5074. Степени вершин по спискам ребер

Задача:

Технические условия:

Входные данные:

Выходные данные:

Результат на C++

Результат на Java

Код на C++:

Код на Java:

Описание:

Related Images:

e-olimp 5080. Количество висячих вершин 1

Related Images: