Задача

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

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

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Тесты

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

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

3 1
0 0 1
0 0 0
1 0 0

4 2
0 1 0 0
1 0 0 1
0 0 0 1
0 1 1 0

6 2
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
1 1 0 0 0 0

4 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

5 3
0 1 0 0 1
1 0 1 0 1
0 1 0 1 0
0 0 1 0 1
1 1 0 1 0

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

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

public class Main {

    private static int count = 0;

    private static void dfs(ArrayList<Integer>[] adj, boolean[] was, int v) {
        count++;
        for (int e: adj[v]) {
            if (!was[e]) {
                was[e] = true;
                dfs(adj, was, e);
            }
        }
    }

    private static void dfs(ArrayList<Integer>[] adj, int v) {
        boolean[] was = new boolean[adj.length];
        was[v] = true;
        dfs(adj, was, v);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt() - 1;
        ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                int d = scanner.nextInt();
                if (d == 1) {
                    adj[i].add(j);
                }
            }
        }
        dfs(adj, v);
        System.out.println(count);
    }
}

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

private static int count = 0;

private static void dfs(ArrayList<Integer>[] adj, boolean[] was, int v) {

count++;

for (int e: adj[v]) {

if (!was[e]) {

was[e] = true;

dfs(adj, was, e);

}

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

boolean[] was = new boolean[adj.length];

was[v] = true;

dfs(adj, was, v);

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int v = scanner.nextInt() - 1;

ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];

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

adj[i] = new ArrayList<>();

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

int d = scanner.nextInt();

if (d == 1) {

adj[i].add(j);

}

dfs(adj, v);

System.out.println(count);

}

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

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа, $c$ будет искомым числом.

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

Условие

Как известно, Андрей Сергеевич — ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой собраны со всего мира. Будем считать, что в мире существует 2000000000 видов бабочек.

Чтобы не запутаться, Андрей Сергеевич присвоил каждому виду уникальный номер. Нумерация бабочек всегда начинается с единицы.

Теперь он хочет знать, есть ли бабочка с видом K в его коллекции, или же её придётся добывать, затрачивая уйму сил и денег.

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

В первой строке входного файла содержится единственное число N (1 ≤ N≤ 100000) — количество видов бабочек в коллекции Андрея Сергеевича.

В следующей строке через пробел находятся N упорядоченных по возрастанию чисел — номера видов бабочек в коллекции.

Все виды бабочек в коллекции имеют различные номера.

В третьей строке файла записано число M (1≤ M≤ 100000) — количество видов бабочек, про которых Андрей Сергеевич хочет узнать, есть ли они у него в коллекции или же нет. В последней строке входного файла содержатся через пробел M чисел — номера видов бабочек, наличие которых необходимо проверить.

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

Выходной файл должен содержать M строчек. Для каждого запроса выведите «YES«, если бабочка с данным номером содержится в коллекции, и «NO» — в противном случае.

Тесты:

№	Входные данные	Выходные данные:
1	7 10 47 50 63 89 90 99 4 84 33 10 82	NO NO YES NO
2	10 1 4 7 11 12 43 44 67 344 355 5 1 2 4 44 45	YES NO YES YES NO

Код на Java:

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

class Main {
	public static boolean find(int search, int[] arr, int len) {
		boolean ret = false;
		int fst = 0;
		int lst = len - 1;
		while (fst <= lst) {
			int mid = (fst + lst) / 2;
			if (search == arr[mid]) {
				ret = true;
				break;
			} else if (search < arr[mid]) {
				lst = mid - 1;
			} else {
				fst = mid + 1;
			}
		}
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int len = scan.nextInt();
		int[] arr = new int[len];
		int i;
		for (i = 0; i < len; i++) {
			arr[i] = scan.nextInt();
		}
		int num = scan.nextInt();
		int search;
		for (i = 0; i < num; i++) {
			search = scan.nextInt();
			System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

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

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

int search;

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

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Алгоритм:

Вначале считываем необходимые нам значения: размер коллекции len, элементы коллекции (массив arr) и количество проверяемых экспонатов num:

Scanner scan = new Scanner(System.in);
int len = scan.nextInt();
int[] arr = new int[len];
int i;
for (i = 0; i < len; i++) {
	arr[i] = scan.nextInt();
}
int num = scan.nextInt();

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

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

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:

int search;
for (i = 0; i < num; i++) {
	search = scan.nextInt();
	System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
}

int search;

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

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Суть алгоритма бинарного поиска: искомый элемент сравнивается с элементом в середине диапазона. При совпадении поиск считаем оконченным. Если совпадения нет, то, в зависимости от различия, поиск продолжается в «левой» или «правой» половине текущего диапазона. Если оказалось, что очередной диапазон имеет «нулевую» длину, это означает, что искомого элемента в исходном массиве нет. Примечание: алгоритм требует упорядоченности исходного массива по возрастанию или убыванию.

public static boolean find(int search, int[] arr, int len) {
	boolean ret = false;
	int fst = 0;
	int lst = len - 1;
	while (fst <= lst) {
		int mid = (fst + lst) / 2;
		if (search == arr[mid]) {
			ret = true;
			break;
		} else if (search < arr[mid]) {
			lst = mid - 1;
		} else {
			fst = mid + 1;
		}
	}
	return ret;
}

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

Ссылки:

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

java@Cat

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

Category Archives: A. Поиск

e-olymp 4000. Обход в глубину

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 3966. An ardent collector of butterflies

Условие

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

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

Тесты:

Код на Java:

Алгоритм:

Ссылки: