Flipping Cards#7538

Flipping Cards (Editorial)

Each picture depicted on the cards will be assigned one vertex of the graph. Each card will be assigned an undirected edge (that connects the vertices corresponding to the pictures on the sides of the card). The resulting graph may be disconnected.

The answer to the problem will be possible if each connected component of the graph contains at most one cycle. Finding the connected components and counting the number of cycles in them can be done using a system of disjoint sets.

Example

Consider four cards. In yellow we denote the sides of the cards with which they will lie up. Let's mark the edge of the graph with a picture with which the corresponding card will lie up.

Consider the case with two connected components:

Algorithm implementation

Define arrays for data processing. The $d s u$ array is used for the disjoint set system. If $i$ is a representative of a set, then $ha s_cy c l e [i]$ has\_cycle[i] contains information about the number of cycles in it:

$ha s_cy c l e [i] = 0$ has\_cycle[i] = 0, no cycles;
$ha s_cy c l e [i] = 1$ has\_cycle[i] = 1, one cycle;
$ha s_cy c l e [i] > 1$ has\_cycle[i] > 1, more than one cycle;

#define MAX 50010
int dsu[2*MAX], has_cycle[2*MAX];

The function Repr returns a representative of the set that contains vertex $n$ .

int Repr(int n)
{
  if (n == dsu[n]) return n;
  return dsu[n] = Repr(dsu[n]);
}

The function Union joins the sets containing the vertices $x$ and $y$ .

void Union(int x, int y)
{
  int x1 = Repr(x), y1 = Repr(y);

If $x$ and $y$ already belong to the same connected component (they have the same representative), and there is an edge $(x, y)$ , then another cycle is formed. Add 1 to the number of cycles of their representative ( $x_{1}$ x_1 is a representative of $x$ and $y$ ):

  if (x1 == y1)
    has_cycle[x1]++;

If $x$ and $y$ belong to different connected components, and $y_{1}$ y_1 becomes a representative of the set, then we add the number of cycles for $x_{1}$ x_1 to the number of cycles for $y_{1}$ y_1.

  else
  {
    dsu[x1] = y1;
    has_cycle[y1] += has_cycle[x1];
  }
}

The main part of the program. Read the input data.

scanf("%d",&tests);
while (tests--)
{
  scanf("%d",&n);

Initialize the system of disjoint sets.

  for(i = 1; i <= 2*n; i++)
  {
    dsu[i] = i;
    has_cycle[i] = 0;
  }

Construct a system of disjoint sets.

  for (i = 0; i < n; i++) 
  {
    scanf("%d %d",&p,&q);
    Union(p,q);
  }

Check if at least one connected component contains more than one cycle.

  for (i = 1; i <= 2*n; i++)
    if (has_cycle[i] > 1) break;

Print the answer.

  printf("%s\n",((i <= 2 * n) ? "impossible" : "possible"));
}