e-olymp 982. Связность

Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.

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

В первой строке заданы количество вершин $n$ и ребер $m$ в графе соответственно $(1 \leq n \leq 100, 1 \leq m \leq 10000)$ . Каждая из следующих m строк содержит по два числа $u_i$ и $v_i$ $(1 \leq u_i, v_i \leq n);$ каждая такая строка означает, что в графе существует ребро между вершинами $u_i$ и $v_i$ .

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

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

Тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	5 4 1 2 5 3 4 5 3 4	NO
3	5 4 1 2 5 1 3 5 4 3	YES

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

import java.util.*;
 
class Graph {
    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
 
        ArrayList<Integer> gr[] = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            gr[i] = new ArrayList<>();
        }
 
        int s = 0;
        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            gr[u - 1].add(v - 1);
            gr[v - 1].add(u - 1);
        }

        LinkedList<Integer> queue = new LinkedList<>();
        queue.push(s);
        boolean used[] = new boolean[n];
        used[s] = true;
 
        while (!queue.isEmpty()) {
            int v = queue.peek();
            queue.pop();
            for (int i = 0; i < gr[v].size(); ++i) {
                int to = gr[v].get(i);
                if (!used[to]) {
                    used[to] = true;
                    queue.push(to);
                }
            }
        }
        String answer = "YES";
        for (int i = 0; i < used.length; i++) {
            if (used[i] == false) {
                answer = "NO";
            }
        }
        System.out.println(answer);
    }
}

import java.util.*;

class Graph {

public static void main(String[] args) {

int n, m;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt();

m = scanner.nextInt();

ArrayList<Integer> gr[] = new ArrayList[n];

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

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

}

int s = 0;

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

int u, v;

u = scanner.nextInt();

v = scanner.nextInt();

gr[u - 1].add(v - 1);

gr[v - 1].add(u - 1);

}

LinkedList<Integer> queue = new LinkedList<>();

queue.push(s);

boolean used[] = new boolean[n];

used[s] = true;

while (!queue.isEmpty()) {

int v = queue.peek();

queue.pop();

for (int i = 0; i < gr[v].size(); ++i) {

int to = gr[v].get(i);

if (!used[to]) {

used[to] = true;

queue.push(to);

}

String answer = "YES";

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

if (used[i] == false) {

answer = "NO";

}

System.out.println(answer);

}

Алгоритм

Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.

Ссылка на Ideone

Facebook
X
Shares

java@Cat

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

e-olymp 982. Связность

Добавить комментарий Отменить ответ