Підпал#4369

Підпал (Розбір)

Для розв'язання задачі необхідно запустити пошук в ширину з кількох джерел. Для цього помістимо всі точки підпалу в чергу, після чого запустимо алгоритм.

Приклад

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

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

Оголосимо робочі масиви.

vector<int> dist;
vector<vector<int> > g;
queue<int> q;

Функція bfs виконує пошук в ширину. Всі джерела цього пошуку заздалегідь поміщені в чергу $q$ .

void bfs(void)
{
  while (!q.empty())
  {
    int v = q.front(); q.pop();
    for (int to : g[v])
      if (dist[to] == -1)
      {
        q.push(to);
        dist[to] = dist[v] + 1;
      }
  }
}

C++

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

scanf("%d %d",&n,&m);
g.resize(n+1);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&u,&v);
  g[u].push_back(v);
  g[v].push_back(u);
}

C++

Значення $d i s t [i]$ містить час, через який загориться вершина $i$ . Спочатку всі значення $d i s t [i]$ дорівнюють $- 1$ .

dist = vector<int>(n+1,-1);

Читаємо номери вершин, що є джерелами підпалу. Для кожної такої вершини $i d$ встановлюємо $d i s t [i d] = 0$ dist[id] = 0 і додаємо її до черги.

scanf("%d",&k);
for(i = 0; i < k; i++)
{
  scanf("%d",&id);
  dist[id] = 0;
  q.push(id);
}

C++

Запускаємо пошук в ширину.

bfs();

Знайдемо вершину $i d$ , яка загориться останньою. Змінна mx містить час, через який відбудеться її загоряння.

mx = -1;
for(i = 1; i <= n; i++)
  if (dist[i] > mx)
  {
    mx = dist[i];
    id = i;
  }

C++

Спочатку виводимо значення $d i s t [i d]$ dist[id] — час, коли загориться остання вершина. Потім виводимо номер вершини $i d$ .

printf("%d\n",dist[id]);
printf("%d\n",id);

Java реалізація

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;
  static Queue<Integer> q = new LinkedList<Integer>();  
  static int dist[];
  static int n, m;
   
  static void bfs()
  {
    while(!q.isEmpty())
    {
      int v = q.poll();
      for(int i = 0; i < g[v].size(); i++)
      {
        int to = g[v].get(i);
        if (dist[to] == -1)
        {
          q.add(to);
          dist[to] = dist[v] + 1;
        }
      }
    }
  }
  
  @SuppressWarnings("unchecked")  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt(); m = con.nextInt();
    
    g = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
    
    dist = new int[n+1];
 
    for (int i = 0; i < m; i++)
    {
      int u = con.nextInt();
      int v = con.nextInt();
      g[u].add(v);
      g[v].add(u);
    }

    Arrays.fill(dist,-1);    
    int k = con.nextInt();
    for (int i = 0; i < k; i++)
    {
      int id = con.nextInt();
      dist[id] = 0;
      q.add(id);
    }
    
    bfs();

    int max = -1, id = -1;
    for(int i = 1; i <= n; i++)
      if (dist[i] > max)
      {
        max = dist[i];
        id = i;
      }

    System.out.println(dist[id]);
    System.out.println(id);
    con.close();
  }
}

Java