Задача взята с сайта 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

Facebook
X
Shares

4 thoughts on “e-olymp 5082. Degrees of vertices”

Ошибка компиляции. Похоже Вы не весь код перенесли в отчёт.

Ответить

Владислав Козачков says: 08/07/2016 at 14:59

Исправил

Ответить

Можно ускорить в два раза если читать строку целиком и считать в ней единицы. Тогда решение укладывается в лимит времени.

class Main {
	public static void main (String[] args) {
		java.util.Scanner scan = new java.util.Scanner(System.in);
		int n = scan.nextInt();
		scan.nextLine();
		for(int i = 0; i < n; i++) {
			String x;
			x = scan.nextLine();
			int count = 0, from = -1;
			while((from = x.indexOf('1', from + 1)) >= 0) count++;
			System.out.print(count + " ");
		}
	}
}

class Main {

public static void main (String[] args) {

java.util.Scanner scan = new java.util.Scanner(System.in);

int n = scan.nextInt();

scan.nextLine();

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

String x;

x = scan.nextLine();

int count = 0, from = -1;

while((from = x.indexOf('1', from + 1)) >= 0) count++;

System.out.print(count + " ");

}

Если же аккуратно сделать тоже самое на С++, то можно легко побить все рекорды скорости по этой задаче.

Ответить

Владислав Козачков says: 13/07/2016 at 21:08

Спасибо, так действительно быстрее работает. Подправить пост или оставить все как есть?

Ответить

java@Cat

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

e-olymp 5082. Degrees of vertices