e-olymp 2270. Поиск цикла

02/12/2020 by Наташа Писаревская

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

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

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$^$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$^$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

№	Входные данные	Выходные данные
1	2 2 1 2 1 2	NO
2	2 2 1 2 2 1	YES 1 2
3	6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2	YES 2 4 6 5
4	6 6 1 3 2 4 3 4 1 2 3 5 3 6	NO
5	4 4 1 3 4 2 2 3 3 4	YES 3 4 2

import java.util.*;
public class Main {
    public static int n, m, flag = 0;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static ArrayList<Integer> used = new ArrayList<Integer>();
    public static ArrayList<Integer> path = new ArrayList<Integer>();
    // поиск в глубину для каждой вершины
    static void dfs(int v) {
        if (flag == 1) return; // если уже нашли цикл, то останавливаемся
        else {
            used.set(v, 1); // посещаем вершину
            path.add(v); // добавляем ее в порядок обхода графа
            for (int i = 0; i < graph.get(v).size(); i++) {
                int to = graph.get(v).get(i); // следующая вершина графа
                if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                    path.add(to); // добавляем следующую вершину в порядок обхода графа
                    flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                    return;
                }
                else dfs(to); // если не посетили, то посещаем
                if (flag == 1) return; // если нашли цикл, то останавливаемся
            }
            used.set(v, 2); // если не нашли цикл, то выходим из вершины
            path.remove(path.size() - 1);
        }
    }
    // проверяем вершины на наличие цикла
    static void checkNodes() {
        for (int i = 0; i <= n; i++) {
            if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее
                dfs(i);
                if (flag == 1) return; // если нашли цикл, то останавливаемся
            }
        }
    }
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        // считываем количество вершин и ребер
        n = s.nextInt();
        m = s.nextInt();
        for (int i = 0; i <= n; i++) {
            used.add(0);
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            // считываем ребра и заполняем граф
            int v1 = s.nextInt();
            int v2 = s.nextInt();
            graph.get(v1).add(v2);
        }
        checkNodes(); // проверяем вершины на наличие цикла
        if (flag == 1) { // если цикл найден
            int i = path.size() - 2; // последняя вершина цикла
            int to = path.get(path.size() - 1); // вершина в которой зациклились
            while (path.get(i) != to) { // получаем индекс вершины в которой зациклились
                i--;
            }
            System.out.println("YES");
            while (i < path.size() - 1) {  // выводим сам цикл
                System.out.print(path.get(i) + " ");
                i++;
            }
            System.out.println();
        }
        else
            System.out.print("NO");
    }
}

import java.util.*;

public class Main {

public static int n, m, flag = 0;

public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

public static ArrayList<Integer> used = new ArrayList<Integer>();

public static ArrayList<Integer> path = new ArrayList<Integer>();

// поиск в глубину для каждой вершины

static void dfs(int v) {

if (flag == 1) return; // если уже нашли цикл, то останавливаемся

else {

used.set(v, 1); // посещаем вершину

path.add(v); // добавляем ее в порядок обхода графа

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

int to = graph.get(v).get(i); // следующая вершина графа

if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл

path.add(to); // добавляем следующую вершину в порядок обхода графа

flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся

return;

}

else dfs(to); // если не посетили, то посещаем

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

used.set(v, 2); // если не нашли цикл, то выходим из вершины

path.remove(path.size() - 1);

}

// проверяем вершины на наличие цикла

static void checkNodes() {

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

if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее

dfs(i);

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

public static void main (String[] args) {

Scanner s = new Scanner(System.in);

// считываем количество вершин и ребер

n = s.nextInt();

m = s.nextInt();

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

used.add(0);

graph.add(new ArrayList<>());

}

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

// считываем ребра и заполняем граф

int v1 = s.nextInt();

int v2 = s.nextInt();

graph.get(v1).add(v2);

}

checkNodes(); // проверяем вершины на наличие цикла

if (flag == 1) { // если цикл найден

int i = path.size() - 2; // последняя вершина цикла

int to = path.get(path.size() - 1); // вершина в которой зациклились

while (path.get(i) != to) { // получаем индекс вершины в которой зациклились

i--;

}

System.out.println("YES");

while (i < path.size() - 1) { // выводим сам цикл

System.out.print(path.get(i) + " ");

i++;

}

System.out.println();

}

else

System.out.print("NO");

}

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).

В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.

Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.

Ссылки

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

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

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
Код решения

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

09/11/2018 by Кирилл Волков

Задача

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

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

В первой строке содержится количество вершин графа $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	2
4 2 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0	4
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	3
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	1
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	5

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

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
Решение на e-olymp
Код решения на Ideone

java@Cat

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

Tag Archives: DFS

e-olymp 2270. Поиск цикла

Задача

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

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

Тесты

№

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

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

Решение

Ссылки

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

Задача

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

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

Тесты

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

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

Ссылки

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

Задача

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

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

Тесты

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

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

Ссылки