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

27/12/2018 by Дима Мороз

Задача

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

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

В первой строчке находится число $N (1 ≤ N ≤ 1000)$. В следующих $N$ строчках находится матрица смежности.

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

Выведите $N$ чисел – степени всех вершин.

Тесты

Входные данные	Выходные данные
2 0 1 1 0	1 1
3 0 1 0 1 0 1 0 1 0	1 2 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 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

Код программы

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

class Main
{
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);
	static int nextInt() throws IOException  {
		in.nextToken();
		return (int)in.nval;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		int n = nextInt();
		for (int i = 0; i < n; i++) {
			int counter = 0, x;
			for (int j = 0; j < n; j++) {
				x = nextInt();
				if (x > 0) counter += (i == j ? 2 : 1);
			}
			out.print (counter + " ");
			out.flush();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static PrintWriter out = new PrintWriter(System.out);

static int nextInt() throws IOException {

in.nextToken();

return (int)in.nval;

}

public static void main (String[] args) throws java.lang.Exception

{

int n = nextInt();

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

int counter = 0, x;

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

x = nextInt();

if (x > 0) counter += (i == j ? 2 : 1);

}

out.print (counter + " ");

out.flush();

}

Решение задачи

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

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

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

25/12/2018 by Карина Миловская

Задача

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $1.$

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

В первой строке находится число $n$ $\left ( 1 \leq n \leq 1000 \right ).$ В следующих $n$ строках находится матрица смежности.

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

Выведите количество висячих вершин в графе.

Тесты

Входные данные	Выходные данные
$2 \\ 0 \ 1 \\ 1 \ 0$	$2$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 1 \ 0$	$0$
$4 \\ 1 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1$	$4$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 0 \ 0$	$1$

Код программы

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int [][] gr = new int [1001][1001]; 
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); 
		int ans = 0; 
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				gr[i][j] =  in.nextInt(); 
			}
		}
		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++;
		}
		System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int [][] gr = new int [1001][1001];

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int ans = 0;

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

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

gr[i][j] = in.nextInt();

}

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++;

}

System.out.println(ans);

}

Решение

Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olymp 5082. Degrees of vertices

06/07/2016 by Владислав Козачков

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

Условие

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

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

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

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

Выведите $N$ чисел – степени всех вершин.

Тесты :

Ввод	Вывод
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 1 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

Код на Java:

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int N;
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		String strout = new String();
		for (int i = 0; i < N; i++) {
			int counter = 0;
			int x;
			for (int j = 0; j < N; j++) {
				x = scan.nextInt();
				if (x > 0) counter += (i == j? 2 : 1);
			}
			strout += counter + " ";
		}
		System.out.print(strout);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int N;

Scanner scan = new Scanner(System.in);

N = scan.nextInt();

String strout = new String();

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

int counter = 0;

int x;

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

x = scan.nextInt();

if (x > 0) counter += (i == j? 2 : 1);

}

strout += counter + " ";

}

System.out.print(strout);

}

Алгоритм:

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

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

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

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

Задача

Тесты

Код программы

Решение задачи

Ссылки

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

Задача

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

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

Тесты

Код программы

Решение

Ссылки

e-olymp 5082. Degrees of vertices

Условие

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

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

Тесты :

Код на Java:

Алгоритм:

Ссылки: