Coloured rain#994

Coloured rain (Editorial)

The problem reduces to analyzing an undirected graph given by its adjacency matrix.

The hills are considered as vertices of the graph, and the bridges as edges between them. The adjacency matrix $g [i] [j]$ g[i][j] indicates whether there is a bridge between vertices $i$ and $j$ . The color of the $i$ -th hill is stored in the array cell $co l [i]$ .

The task is to find the number of "bad" bridges. A bridge is considered bad if it connects two hills of different colors, i.e., for an edge $(i, j)$ , the condition $co l [i] \neq = co l [j]$ col[i] \ne col[j] holds.

Since the graph is undirected, each edge is counted only once, so we consider only pairs $(i, j)$ where $i < j$ i < j.

Algorithm implementation

Declare the adjacency matrix $g$ and the color array $co l$ .

#define MAX 110
int g[MAX][MAX], col[MAX];

Read the adjacency matrix of the graph.

scanf("%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
  scanf("%d", &g[i][j]);

Read the array of hill colors.

for (i = 0; i < n; i++)
  scanf("%d", &col[i]);

Compute in the variable $r es$ the number of such pairs of hills $(i, j)$ between which a bridge exists $(g [i] [j] = 1)$ (g[i][j] = 1) and for which $co l [i] \neq = co l [j]$ col[i] \ne col[j].

res = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
  if ((g[i][j] == 1) && (col[i] != col[j])) res++;

To avoid counting the same pair twice (as $(i, j)$ and $(j, i)$ ), the final value of res should be divided by two.

res /= 2;

Print the answer.

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