e-olymp 5071. Проверка на неориенитрованность

03/01/2019 by Кирилл Бондаренко

Задача. Проверка на неориенитрованность

Условие задачи
По заданной квадратной матрице $n\times n$ из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

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

Входной файл содержит число $n(1\leq n\leq 100)$ — размер матрицы, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — саму матрицу.

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

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
3 0 1 1 1 0 1 1 1 0	YES
3 0 1 0 1 0 1 1 1 0	NO
3 0 1 0 1 1 1 0 1 0	NO
4 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1	NO

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = n*n;
		int [] G = new int [k];
		for (int i = 0; i < G.length; i++) {
			G[i] = in.nextInt();
		}
		int j = 0, c = 0, s = 0;
		boolean f = true;
		for (int i = 0; i < k; i++) {
			if (G[i] != G[j]) {
				f=false;
				break;
			}
			if (c == n - 1) {
				c = 0;
				s++;
				j = s;
			} else {
				j = j + n;
				c++;
			}
		}
		for (int i = 0; i < k; i = i + n + 1) {
			if (G[i] != 0) {
				f = false;
				break;
			}
		}
		if (f) System.out.print("YES"); else System.out.print("NO");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main {

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

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = n*n;

int [] G = new int [k];

for (int i = 0; i < G.length; i++) {

G[i] = in.nextInt();

}

int j = 0, c = 0, s = 0;

boolean f = true;

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

if (G[i] != G[j]) {

f=false;

break;

}

if (c == n - 1) {

c = 0;

s++;

j = s;

} else {

j = j + n;

c++;

}

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

if (G[i] != 0) {

f = false;

break;

}

if (f) System.out.print("YES"); else System.out.print("NO");

}

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

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: $a[i] = a[j]$. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

e-olymp 977. Дерево?

26/12/2018 by Костя Григорян

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

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

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

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

Выведите сообщение YES, если граф является деревом, и NO в противном случае.

Тесты

Входные данные	Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex]	[latex]NO[/latex]
[latex]1 \\ 0[/latex]	[latex]YES[/latex]

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

import java.util.Scanner;
import java.util.ArrayList;

class Main
{
	private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {
		A[v]++;
		if (A[v]>1)
			return;
		for (int i=0; i<g.get(v).size(); i++)
		{
			if (g.get(v).get(i)!=p)
				dfs(g.get(v).get(i), v, g, A);
		}
	}
	
	public static void main (String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] A = new int[n];
		ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i<n; i++) {
			ArrayList<Integer> r = new ArrayList<Integer>();
			for (int j=0; j<n; j++) {
				int a = scanner.nextInt();
				if (a==1) {
					r.add(j);
				}
			}
			g.add(r);
		}
		int t=0;
		dfs(0, -1, g, A);
		for (int i=0; i<n; i++)
		{
			if (A[i]!=1)
			{
				t++;
				break;
			}
		}
		if (t!=0)
			System.out.print("NO");
		else
			System.out.print("YES");
	}
}

import java.util.Scanner;

import java.util.ArrayList;

class Main

{

private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {

A[v]++;

if (A[v]>1)

return;

for (int i=0; i<g.get(v).size(); i++)

{

if (g.get(v).get(i)!=p)

dfs(g.get(v).get(i), v, g, A);

}

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] A = new int[n];

ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();

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

ArrayList<Integer> r = new ArrayList<Integer>();

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

int a = scanner.nextInt();

if (a==1) {

r.add(j);

}

g.add(r);

}

int t=0;

dfs(0, -1, g, A);

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

{

if (A[i]!=1)

{

t++;

break;

}

if (t!=0)

System.out.print("NO");

else

System.out.print("YES");

}

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

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

Условие задачи на e-olymp
Код решения

ML3

09/12/2017 by Сидоровский Дмитрий

Задача

Дана длина ребра куба. Найти объем куба и площадь его полной поверхности.

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

Длина ребра куба $latex a$.

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

Объем куба и площадь его полной поверхности.

Тесты

a	V	S
1.7	4.91299	17.34
3	27	54
5	125	150

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a, V, S;
		Scanner in = new Scanner(System.in);
		a = in.nextDouble();
		V = a*a*a;
		S = 6*a*a;
		System.out.println(V);
		System.out.println(S);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double a, V, S;

Scanner in = new Scanner(System.in);

a = in.nextDouble();

V = a*a*a;

S = 6*a*a;

System.out.println(V);

System.out.println(S);

}

Решение

Задаем длину ребра куба и получаем объем куба и площадь его полной поверхности согласно формулам: $latex V=a^3$ и $latex S=6a^2$.

Пример работы программы можно увидеть на ideone.

java@Cat

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

Tag Archives: ребро

e-olymp 5071. Проверка на неориенитрованность

Задача. Проверка на неориенитрованность

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

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

Тесты

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

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

e-olymp 977. Дерево?

Задача

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

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

Тесты

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

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

Ссылки

ML3

Задача

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

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

Тесты

Решение