977. Дерево?

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

Вход. Первая строка содержит количество вершин графа n (1 ≤ n ≤ 100). Далее записана матрица смежности размером n × n, в которой 1 обозначает наличие ребра, 0 – его отсутствие. Матрица симметрична относительно главной диагонали.

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

Пример входа	Пример выхода
3 0 1 0 1 0 1 0 1 0	YES

РЕШЕНИЕ

графы – поиск в глубину

Анализ алгоритма

Граф из n вершин является деревом тогда и только тогда, когда:

1. Граф связный. Запустим поиск в глубину из первой вершины. Подсчитаем количество посещенных вершин в процессе поиска. Если оно равно n, то граф является связным.

2. |V| = |E| + 1. Если граф является деревом, то он содержит n – 1 ребро.

3. Граф не содержит циклов. Запустим поиск в глубину из первой вершины. Если существует обратное ребро, то граф имеет цикл и не является деревом.

Выполнение условий 1) и 2) или 1) и 3) достаточно для того, чтобы граф являлся деревом.

Пример

Граф, приведенный в примере, является деревом.

Реализация алгоритма – проверка условий 1) и 3)

Объявим матрицу смежности графа g и массив used.

#define MAX 110

int g[MAX][MAX], used[MAX];

Функция dfs реализует поиск в глубину из вершины v. Предком вершины v является p. Переменная flag станет равной 1, если будет обнаружен цикл.

void dfs(int v, int p)

{

Если граф уже не является деревом (flag = 1), то нет смысла продолжать поиск.

if (flag) return;

Отмечаем вершину v как пройденную.

used[v] = 1;

Посещена вершина v, увеличиваем c на 1.

c++;

Ребро (v, i) будет обратным и образовывать цикл, если i ≠ p и при этом вершина i уже была пройдена (used[i] = 1). В случае обнаружения цикла установим flag = 1. Если цикла нет, то продолжаем поиск из вершины i.

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

if ((i != p) && g[v][i])

if(used[i]) flag = 1; else dfs(i,v);

}

Основная часть программы. Читаем входные данные.

scanf("%d",&n);

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

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

scanf("%d",&g[i][j]);

В переменной c подсчитываем количество посещенных вершин при поиске в глубину. Установим flag = 0, если в графе нет цикла. При обнаружении цикла flag станет равным 1.

c = 0;

flag = 0;

Все вершины изначально являются непройденными (обнуляем массив used).

memset(used,0,sizeof(used));

Запускаем поиск в глубину из нулевой вершины. Поскольку она является корнем дерева поиска, то не имеет родителя. В качестве второго аргумента передаем функции dfs значение -1.

dfs(0,-1);

Граф не будет деревом, если существует обратное ребро (flag = 1) или граф не является связным (c ≠ n).

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Реализация алгоритма – проверка условий 1) и 2)

Объявим матрицу смежности графа g и массив used.

#define MAX 101

int g[MAX][MAX], used[MAX];

Функция dfs реализует поиск в глубину из вершины v.

void dfs(int v)

{

Отмечаем вершину v как пройденную.

used[v] = 1;

Посещена вершина v, увеличиваем c на 1.

c++;

Перебираем вершины i, куда можно двигаться из v. Передвижение из v в i возможно, если:

· существует ребро (v, i), то есть g[v][i] = 1;

· вершина i еще не пройдена (used[i] = 0)

Если оба условия верны, то продолжаем поиск в глубину из вершины i.

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

if (g[v][i] && !used[i]) dfs(i);

}

Основная часть программы. Читаем входное значение n.

scanf("%d", &n);

Количество ребер в графе подсчитываем в переменной Edges.

Edges = 0;

Все вершины изначально являются непройденными (обнуляем массив used).

memset(used, 0, sizeof(used));

Читаем матрицу смежности g. Подсчитываем количество ребер в графе.

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

{

scanf("%d", &g[i][j]);

Edges += g[i][j];

}

Поскольку граф неориентированный, то ребра (u, v) и (v, u) считаются одинаковыми. Разделим значение Edges на 2.

Edges /= 2;

В переменной c подсчитываем количество посещенных вершин при поиске в глубину.

c = 0;

Запускаем поиск в глубину из вершины 1.

dfs(1);

Граф является деревом, если количество ребер в нем равно n – 1, а также если он связный (c = n).

if ((Edges == n - 1) && (c == n)) printf("YES\n");

else printf("NO\n");

Java реализация

import java.util.*;

//import java.io.*;

public class Main

{

static int c = 0;

static int m[][], used[];

static void dfs(int v)

{

used[v] = 1; c++;

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

if (m[v][i]== 1 && used[i] == 0) dfs(i);

}

public static void main(String[] args) //throws IOException

{

Scanner con = new Scanner(System.in);

//Scanner con = new Scanner(new FileReader ("977.in"));

int n = con.nextInt();

m = new int[n][n];

used = new int[n];

Arrays.fill(used, 0);

int Edges = 0;

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

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

{

m[i][j] = con.nextInt();

Edges += m[i][j];

}

dfs(0); Edges /= 2;

if ((Edges == n - 1) && (c == n))

System.out.printf("YES");

else

System.out.printf("NO");

}

}

Python реализация – проверка условий 1) и 3)

Функция dfs реализует поиск в глубину из вершины v. Предком вершины v является p. Переменная flag станет равной 1, если будет обнаружен цикл.

def dfs(v, p):

Объявим глобальные переменные, используемые функцией.

global flag, c

Если граф уже не является деревом (flag = 1), то нет смысла продолжать поиск.

if flag: return

Отмечаем вершину v как пройденную.

used[v] = 1

Посещена вершина v, увеличиваем c на 1.

c += 1

Ребро (v, i) будет обратным и образовывать цикл, если i ≠ p и при этом вершина i уже была пройдена (used[i] = 1). В случае обнаружения цикла установим flag = 1. Если цикла нет, то продолжаем поиск из вершины i.

for i in range(n):

if i != p and g[v][i]:

if used[i]: flag = 1

else: dfs(i, v)

Основная часть программы. Читаем входное значение n.

n = int(input())

В переменной c подсчитываем количество посещенных вершин при поиске в глубину. Установим flag = 0, если в графе нет цикла. При обнаружении цикла flag станет равным 1.

c = 0

flag = 0

Все вершины изначально являются непройденными (список used заполняем нулями).

used = [0] * n

Создаем матрицу смежности g, изначально заполняем ее нулями.

g = [[0] * n for _ in range(n)]

Читаем входную матрицу смежности.

for i in range(n):

g[i] = list(map(int, input().split()))

Запускаем поиск в глубину из вершины 0.

dfs(0, -1)

Граф не будет деревом, если существует обратное ребро (flag = 1) или граф не является связным (c ≠ n).

if flag or c != n:

print("NO")

else:

print("YES")

Python реализация – проверка условий 1) и 2)

Функция dfs реализует поиск в глубину из вершины v.

def dfs(v):

global c

Отмечаем вершину v как пройденную.

used[v] = 1

Посещена вершина v, увеличиваем c на 1.

c += 1

Перебираем вершины i, куда можно двигаться из v. Передвижение из v в i возможно, если:

· существует ребро (v, i), то есть g[v][i] = 1;

· вершина i еще не пройдена (used[i] = 0)

Если оба условия верны, то продолжаем поиск в глубину из вершины i.

for i in range(1, n + 1):

if g[v][i] and not used[i]: dfs(i)

Основная часть программы. Читаем входное значение n.

n = int(input())

Количество ребер в графе подсчитываем в переменной Edges.

Edges = 0

Все вершины изначально являются непройденными (список used заполняем нулями).

used = [0] * (n + 1)

Создаем матрицу смежности g, изначально заполняем ее нулями.

g = [[0] * (n + 1) for _ in range(n + 1)]

Читаем матрицу смежности g. В переменной Edges подсчитываем количество ребер в графе.

for i in range(1, n + 1):

g[i] = [0] + list(map(int, input().split()))

Edges += sum(g[i])

Поскольку граф неориентированный, то ребра (u, v) и (v, u) считаются одинаковыми. Разделим значение Edges на 2.

Edges //= 2

В переменной c подсчитываем количество посещенных вершин при поиске в глубину.

c = 0

Запускаем поиск в глубину из вершины 1.

dfs(1)

Граф является деревом, если количество ребер в нем равно n – 1, а также если он связный (c = n).

if Edges == n - 1 and c == n:

print("YES")

else:

print("NO")