Yandırma#4369

Yandırma (Həll təhlili)

Məsələni həll etmək üçün bir neçə mənbədən enliyinə axtarış (BFS) işə salmaq lazımdır. Bunun üçün bütün yanğın nöqtələrini növbəyə yerləşdiririk, bundan sonra isə alqoritmi işə salırıq.

Misal

Misalda verilmiş qraf aşağıdakı görünüşə malikdir:

Alqoritmin reallaşdırılması

İşçi massivləri elan edək.

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

bfs funksiyası enliyinə axtarışı yerinə yetirir. Bu axtarışın bütün mənbələri əvvəlcədən $q$ növbəsinə yerləşdirilib.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Qrafı qururuq.

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]$ dəyəri $i$ təpəsinin alışacağı vaxtı özündə saxlayır. Əvvəlcə bütün $d i s t [i]$ dəyərləri $- 1$ -ə bərabərdir.

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

Yanğın mənbəyi olan təpələrin nömrələrini oxuyuruq. Belə hər bir $i d$ təpəsi üçün $d i s t [i d] = 0$ dist[id] = 0 təyin edirik və onu növbəyə əlavə edirik.

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

C++

Enliyinə axtarışı işə salırıq.

bfs();

Ən son alışacaq $i d$ təpəsini tapaq. mx dəyişəni onun alışmasına qədər keçəcək vaxtı özündə saxlayır.

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

C++

Əvvəlcə $d i s t [i d]$ dist[id] dəyərini — son təpənin alışacağı vaxtı çap edirik. Sonra isə $i d$ təpəsinin nömrəsini çap edirik.

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

Java reallaşdırılması

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