Domino#1104

Domino (Həll təhlili)

Gəlin, istiqamətlənmiş qrafda güclü əlaqəli komponentlərin tapılması məsələsinə baxaq. Qrafın hər bir təpəsini eyni güclü əlaqəli komponentdən olan eyni rənglə rəngləyək. $co l or [i]$ color[i] $i$ -ci təpənin rəngini göstərsin. Rəngləmə üçün fərqli rənglərin sayı, güclü bağlı komponentlərin sayına bərabər olacaq.

Aydındır ki, əgər bir domino parçasını itələsək, o güclü əlaqəli komponentdən olan bütün dominolar mütləq yıxılacaq. $c n t$ ilə güclü əlaqəli komponentlərin sayını göstərək.

Uzunluğu $c n t$ olan $u se d$ massivini elan edək, burada $u se d [i] = 1$ used[i] = 1 əgər $i$ -ci əlaqəli komponentdən olan dominonu itələmək lazımdırsa. İndi $u se d [i]$ dəyərlərini $0$ təyin etməyin lazım olduğu hallarını müəyyən edək.

Qrafın bütün kənarlarını şərh edək. Biz yalnız müxtəlif əlaqəli komponentləri birləşdirən kənarları maraqlandırırıq. Əgər belə bir kənar $i \to j$ i \rightarrow j formasındadırsa (burada $co l or [i] \neq = co l or [j]$ color[i] \ne color[j]), onda $u se d [co l or [j]] = 0$ used[color[j]] = 0 təyin edirik. Bu o deməkdir ki, $co l or [i]$ color[i] rəngindən olan komponentdən dominonu itələməklə, $co l or [j]$ color[j] rəngindən olan komponentlərin bütün dominolarını mütləq yıxacağıq.

Bütün kənarları işləndikdən sonra $u se d$ massivində birlərin sayını hesablayır üst. Bu, itələməli olan minimum domino sayıdır.

Misal

Misallarda verilmiş qraflar aşağıdakı kimidir:

Birinci misalda, $1$ nömrəli domino parçasını itələmək kifayətdir.
İkinci misalda, $1$ və $5$ nömrəli dominoları itələmək lazımdır.

Birinci misaldakı qrafın $3$ güclü əlaqəli komponenti var.

Çünki $(1, 2)$ kənarı mövcuddur, $2$ nömrəli domino parçasını itələmək lazım deyil;
Çünki $(2, 3)$ kənarı mövcuddur, $3$ nömrəli domino parçasını itələmək lazım deyil;

Alqoritmin Tətbiqi

Giriş qrafını qonşuluq siyahısında $g$ tipində saxlayarıq.

Əks qrafı (bütün kənarların istiqamətləri dəyişmiş qraf) $g r$ tipində qonşuluq siyahısında saxlayarıq.

vector<vector<int> > g, gr;
vector<int> used, top, color;

dfs1 funksiyası giriş qrafında dərinlik üzrə axtarış həyata keçirir. $t o p$ massivi dərinlik üzrə axtarış prosesində tamamlanmış təpələri münasib qaydada saxlayır.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

C++

dfs2 funksiyası əks qrafda dərinlik üzrə axtarış həyata keçirir. $df s 2$ funksiyası rekursiv olaraq çağırıldıqda ziyarət olunan bütün təpələr bir güclü əlaqəli komponentə aiddir. Bu təpələrin hər birini $c$ rəngi ilə rəngləyirik.

void dfs2(int v, int c)
{
  color[v] = c;
  for (int to : gr[v])
    if (color[to] == -1) dfs2(to, c);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Əks qrafı qururuq.

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

C++

Giriş qrafında dərinlik üzrə axtarışa başlayırıq. Təpələrin emal edilməsi tamamlanma qaydası $t o p$ massivində saxlanılır.

used.resize(n+1);
for(i = 1; i <= n; i++)
  if (!used[i]) dfs1(i);

Sonra əks qrafda dərinlik üzrə axtarış həyata yetiririk. Əks qraf təpələri $t o p$ massivindəki qaydaya uyğun işlənir, sondan başlayaraq (sağdan sola). Bir güclü əlaqəli komponentə aid olan təpələr eyni rəng ilə rənglənir. Cari rəng $c$ dəyişənində saxlanılır.

Əlavə emal üçün, $t o p$ massivini əksinə çevirərək, içindəki təpələri soldan sağa emal edəcəyik.

color.assign(n+1,-1);
reverse(top.begin(), top.end());
c = 0;
for (int v : top)
  if (color[v] == -1) dfs2(v, c++);

$c$ dəyişəni güclü bağlı komponentlərin sayını saxlayır.

used.assign(c,1);
for (i = 1; i < g.size(); i++)
  for (int to : g[i])

Qrafın bütün kənarlarını $(i, t o)$ şərh edirik. Təpələrin $i$ və $t o$ fərqli güclü əlaqəli komponentlərdə olub-olmadığını yoxlayırıq. Bu, əgər onlar müxtəlif rənglərdə rənglənibsə doğrudur. Belə halda, təpə $i$ aid olduğu güclü əlaqəli komponentdəki hər hansı dominonun itələndiyi təqdirdə, həm də $t o$ dominonu yıxılacaq. Bu, $co l or [t o]$ color[to] rəngində olan dominonu itələməyin mənası olmadığını göstərir. Buna görə $u se d [co l or [t o]] = 0$ used[color[to]] = 0 təyin edirik.

    if (color[i] != color[to]) used[color[to]] = 0;

$c$ dəyişənində itələnməli olan domino sayını sayırıq. Əgər hər hansı rəng üçün $i$ $u se d [i] = 1$ used[i] = 1 şərti yerinə yetirilirsə, bu o deməkdir ki, digər rəngdəki başqa domino itələnməkdən asılı olmayaraq, həmin rəngli heç bir domino yıxılmayacaq. Bu halda rəng $i$ olan ən azı bir domino itələmək məcburiyyətində qalacağıq.

c = 0;
for(i = 0; i < used.size(); i++)
  if (used[i]) c++;

Nəticəni ekranlaşdırırıq.

printf("%d\n",c);

Java tətbiqi

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g, gr;	
  static int used[], color[];
  static Vector<Integer> top = new Vector<Integer>();

  static void dfs1(int v)
  {
    used[v] = 1;
    for(int i = 0; i < g[v].size(); i++)
    {
      int to = g[v].get(i);
      if (used[to] == 0) dfs1(to);
    }
    top.add(v);
  }

  static void dfs2(int v, int c)
  {
    color[v] = c;
    for(int i = 0; i < gr[v].size(); i++)
    {
      int to = gr[v].get(i);
      if (color[to] == -1) dfs2(to,c);
    }
  }
  
  @SuppressWarnings("unchecked")  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    
    g = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
    gr = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      gr[i] = new ArrayList<Integer>();
    
    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a].add(b);
      gr[b].add(a);
    }

    used = new int[n+1];
    for(int i = 1; i <= n; i++)
      if (used[i] == 0) dfs1(i);
    
    color  = new int[n+1];
    Arrays.fill(color, -1);
    int c = 0;
    for(int i = 1; i <= n; i++)
    {
      int v = top.get(n-i);
      if (color[v] == -1) dfs2(v,c++);
    }

    used = new int[c];
    Arrays.fill(used, 1);
    for(int i = 1; i < g.length; i++)
    for(int j = 0; j < g[i].size(); j++)
    {
      int to = g[i].get(j);
      // check edge i -> j if they in the same scc.
      if (color[i] != color[to]) used[color[to]] = 0;
    }

    c = 0;
    for(int i = 0; i < used.length; i++)
      if (used[i] == 1) c++;
    
    System.out.println(c);
    con.close();
  }
}

Java