Доміно#1104

Доміно (Розбір)

Розглянемо задачу знаходження сильних компонент зв'язності в орієнтованому графі. Кожну вершину графа з однієї сильної зв'язної компоненти зафарбуємо в один і той же колір. Нехай $co l or [i]$ color[i] позначає колір $i$ -ї вершини. Число різних кольорів забарвлення буде дорівнювати числу компонент сильної зв'язності.

Очевидно, що якщо штовхнути одну кісточку доміно, то обов'язково впадуть всі кісточки, що належать тій же сильній компоненті зв'язності. Позначимо через $c n t$ кількість сильних компонент зв'язності.

Оголосимо масив $u se d$ довжини $c n t$ , де $u se d [i] = 1$ used[i] = 1, якщо необхідно штовхнути доміно з $i$ -ї компоненти зв'язності. Тепер визначимо, для яких значень $u se d [i]$ слід встановити рівним $0$ .

Переберемо всі ребра графа. Нас цікавлять лише ті ребра, які з'єднують різні компоненти зв'язності. Якщо таке ребро має вигляд $i \to j$ i \rightarrow j (де $co l or [i] \neq = co l or [j]$ color[i] \ne color[j]), то встановимо $u se d [co l or [j]] = 0$ used[color[j]] = 0. Це означає, що немає необхідності штовхати доміно з компоненти кольору $co l or [j]$ color[j], оскільки, штовхнувши доміно з компоненти кольору $co l or [i]$ color[i], ми гарантовано зіштовхнемо всі доміно з компоненти кольору $co l or [j]$ color[j].

Після обробки всіх ребер залишається підрахувати кількість одиниць у масиві $u se d$ . Це і буде мінімальна кількість костяшок, які слід штовхнути.

Приклад

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

У першому прикладі достатньо штовхнути доміно номер $1$ .
У другому прикладі необхідно штовхнути доміно з номерами $1$ та $5$ .

Граф із першого прикладу має $3$ сильно зв'язні компоненти.

оскільки існує ребро $(1, 2)$ , немає необхідності штовхати доміно номер $2$ ;
оскільки існує ребро $(2, 3)$ , немає необхідності штовхати доміно номер $3$ ;

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

Вхідний граф зберігаємо у списку суміжності $g$ .

Зворотній граф (граф, у якому змінені всі напрямки ребер) зберігаємо у списку суміжності $g r$ .

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

Функція dfs1 виконує пошук в глибину на вхідному графі. У масив $t o p$ заносимо вершини в порядку завершення їх обробки в процесі пошуку в глибину.

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

C++

Функція dfs2 виконує пошук в глибину на зворотному графі. Усі вершини, які відвідуються в ході рекурсивного виклику функції $df s 2$ , належать одній компоненті сильної зв'язності. Кожну з таких вершин фарбуємо в колір $c$ .

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

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

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

Запускаємо пошук в глибину на вхідному графі. Порядок завершення обробки вершин зберігаємо у масиві $t o p$ .

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

Потім виконуємо пошук в глибину на зворотному графі. Вершини зворотного графа обробляються у порядку, в якому вони знаходяться в масиві $t o p$ , починаючи з кінця (праворуч наліво). Вершини, що належать одній компоненті сильної зв'язності, зафарбовуються в один колір. Поточний колір забарвлення міститься в змінній $c$ .

Для зручності подальшої обробки обернемо масив $t o p$ , після чого будемо обробляти вершини в ньому зліва направо.

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

Змінна $c$ містить кількість компонент сильної зв'язності.

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

Перебираємо всі ребра графа $(i, t o)$ . Перевіряємо, чи знаходяться вершини $i$ і $t o$ в різних сильно зв'язних компонентах. Це так, якщо вони зафарбовані в різні кольори. В такому випадку, якщо штовхнути будь-яке доміно з компоненти сильної зв'язності, до якої належить вершина $i$ , то обов'язково впаде доміно $t o$ . Це означає, що немає сенсу штовхати доміно кольору $co l or [t o]$ color[to]. Тому встановлюємо $u se d [co l or [t o]] = 0$ used[color[to]] = 0.

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

У змінній $c$ підраховуємо кількість доміно, які слід штовхнути. Якщо для якогось кольору $i$ виконується умова $u se d [i] = 1$ used[i] = 1, це означає, що жодне доміно кольору $i$ не впаде, незалежно від того, яке доміно іншого кольору мы штовхнемо. В цьому випадку обов'язково доведеться штовхнути хоча б одне доміно кольору $i$ .

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

Виводимо відповідь.

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

Java реалізація

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