Отримай дерево#978

Отримай дерево (Розбір)

Виконуємо пошук у глибину, починаючи з першої вершини. Будуємо дерево пошуку у глибину та виводимо всі його ребра.

Приклад

Граф, наведений у прикладі, має вигляд:

При запуску пошуку у глибину з вершини $1$ обхід пройде по ребрах: $(1, 2), (2, 3), (3, 4)$ (1, 2), (2, 3), (3, 4).

Реалізація алгоритму

Матрицю суміжності графа зберігаємо в масиві $g$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

Функція dfs виконує пошук у глибину, починаючи з вершини $v$ . Виводимо кожне ребро $(v, i)$ , що входить в дерево пошуку у глибину.

void dfs(int v)
{
  used[v] = 1;
  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i])
    {
      printf("%d %d\n",v,i);
      dfs(i);
    }
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&m);
memset(g,0,sizeof(g)); memset(used,0,sizeof(used));
while(m--)
{
  scanf("%d %d",&a,&b);
  g[a][b] = g[b][a] = 1;
}

C++

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

dfs(1);

Java реалізація

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n, m;
  
  static void dfs(int v)
  {
    used[v] = 1;
    for(int i = 1; i <= n; i++) 
      if (g[v][i] == 1 && used[i] == 0)
      {
        System.out.println(v + " " + i);
        dfs(i);
      }
    used[v] = 2;    
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new int[n+1][n+1];
    used = new int[n+1];
    
    for(int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();      
      g[a][b] = g[b][a] = 1;
    }
    
    dfs(1);
    con.close();
  }
}

Java