Задача

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

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

В первой строке находятся два натуральных числа $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

Задача

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

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

В первой строке содержится количество вершин графа $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: поиск в глубину

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

Задача

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

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

Тесты

№

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

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

Решение

Ссылки

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

Задача

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

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

Тесты

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

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

Ссылки