Dominoes#1104

Dominoes (Editorial)

Let us consider the problem of finding strongly connected components in a directed graph. Each vertex in one strongly connected component will be assigned the same color. Let $co l or [i]$ color[i] denote the color of the $i$ -th vertex. The number of distinct colors will equal the number of strongly connected components.

It is obvious that if one domino tile is pushed, all tiles belonging to the same strongly connected component will inevitably fall. Let $c n t$ represent the number of strongly connected components.

We'll define an array $u se d$ of length $c n t$ , where $u se d [i] = 1$ used[i] = 1 if it is necessary to push a domino in the $i$ -th component. Now, let us determine for which values of $u se d [i]$ we should set it to $0$ .

Iterate through all edges of the graph. We are interested only in the edges that connect different strongly connected components. If such an edge is of the form $i \to j$ i \rightarrow j (where $co l or [i] \neq = co l or [j]$ color[i] \ne color[j]), then set $u se d [co l or [j]] = 0$ used[color[j]] = 0. This means there is no need to push a domino from the component with color $co l or [j]$ color[j], because by pushing a domino from the component with color $co l or [i]$ color[i], we'll guaranteedly topple all dominoes in the component with color $co l or [j]$ color[j].

After processing all edges, count the number of ones in the array $u se d$ . This will be the minimum number of domino tiles that need to be pushed.

Example

The graphs from the examples have the following form:

In the first example, it is enough to push domino number $1$ .
In the second example, it is necessary to push dominoes numbered $1$ and $5$ .

The graph in the first example has $3$ strongly connected components.

Since there is an edge $(1, 2)$ , there is no need to push domino number $2$ ;
Since there is an edge $(2, 3)$ , there is no need to push domino number $3$ ;

Algorithm implementation

The input graph is stored in the adjacency list $g$ .

The reverse graph (a graph where all edge directions are reversed) is stored in the adjacency list $g r$ .

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

The function dfs1 performs a depth-first search on the input graph. Vertices are added to the array $t o p$ in the order of their processing completion during the dfs.

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

C++

The function dfs2 performs a depth-first search on the reverse graph. All vertices visited during a recursive call of $df s 2$ belong to the same strongly connected component. Each of these vertices is assigned the color $c$ .

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

The main part of the program. Read the input data. Construct the reverse graph.

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

Prform a depth-first search on the input graph, storing the order in which vertices finish processing in the array $t o p$ .

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

Next, perform a depth-first search on the reverse graph. The vertices of the reverse graph are processed in the order they appear in the array $t o p$ , starting from the end (right to left). Vertices belonging to the same strongly connected component are assigned the same color. The current color used for coloring is stored in the variable $c$ .

For convenience in further processing, we reverse the array $t o p$ , allowing us to process its vertices from left to right.

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

The variable $c$ contains the number of strongly connected components.

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

Iterate through all edges of the graph $(i, t o)$ . Check whether the vertices $i$ and $t o$ belong to different strongly connected components. This is true if they are colored with different colors. In such a case, if we push any domino from the strongly connected component to which vertex $i$ belongs, domino $t o$ will inevitably fall as well. This means there is no need to push a domino of color $co l or [t o]$ color[to]. Therefore, set $u se d [co l or [t o]] = 0$ used[color[to]] = 0.

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

The variable $c$ keeps track of the number of dominoes that need to be pushed. If for any color $i$ , the condition $u se d [i] = 1$ used[i] = 1 holds, it means that no domino of color $i$ will fall regardless of which domino of another color is pushed. In this case, it will be necessary to push at least one domino of color $i$ .

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

Print the answer.

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

Java implementation

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