Підрахунок витоків (Розбір)

Для розв'язання задачі зручно перейти від списку суміжності до матриці суміжності графа.

Побудуємо матрицю суміжності розміром n \times n, де елемент a_{ij} = 1, якщо існує орієнтоване ребро з вершини $i$ у вершину $j$, і $0$ у протилежному випадку.

Далі для кожної вершини $j$ підрахуємо кількість ребер, що входять до неї. Це можна зробити, просумувавши елементи $j$-го стовпця матриці суміжності.

Вершина є витоком тоді і тільки тоді, коли до неї не входить жодне ребро, тобто сума елементів відповідного стовпця дорівнює $0$.

Таким чином, відповіддю є кількість вершин, для яких число вхідних ребер дорівнює нулю.

Приклад

Граф містить один витік — вершину $4$, оскільки до неї не входить жодне ребро.

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

Оголосимо матрицю суміжності та масив $in$, де $in[i]$ зберігає кількість ребер, що входять у вершину $i$.

#define MAX 101
int g[MAX][MAX], in[MAX];

Читаємо вхідні дані. За заданим списком суміжності будуємо матрицю суміжності.

scanf("%d", \u0026n);
for (i = 1; i \u003c= n; i++)
{

Для кожної вершини $i$ спочатку читаємо кількість ребер $k$, що виходять з неї.

  scanf("%d", \u0026k);
  for (j = 0; j \u003c k; j++)
  {

Для кожного ребра $(i,x)$ встановлюємо g[i][x] = 1.

    scanf("%d", \u0026x);
    g[i][x] = 1;
  }
}

Перебираємо всі пари вершин графа. Для кожного ребра $(i,j)$ збільшуємо значення $in[j]$ на $1$, оскільки ребро $(i,j)$ входить у вершину $j$.

for (i = 1; i \u003c= n; i++)
for (j = 1; j \u003c= n; j++)
  if (g[i][j] == 1) in[j]++;

Підраховуємо кількість вершин-витоків — тобто вершин, у які не входить жодне ребро (для яких in[i] = 0).

int source = 0;
for (i = 1; i \u003c= n; i++)
  if (in[i] == 0) source++;

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

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