Avia marşrutların yoxlanılması (Həll təhlili)

Qrafın güclü şəkildə əlaqəli olub olmadığını yoxlamaq üçün "YES" çıxış verilməlidir. Qraf hər hansı bir zirvə üçün $v$, aşağıdakı şərtləri ödəyəndə güclü şəkildə əlaqəli adlanır:

• zirvədən $v$ qrafın digər zirvələrinə keçmək mümkündür;

• zirvə $v$-ə digər zirvələrdən keçmək mümkündür. Başqa sözlə, hər hansı bir zirvədən $v$-ə yol mövcuddur, bu da əks tərəflər vasitəsilə keçməyin mümkünlüyünü ifadə edir.

Birinci zirvəni v = 1 seçək və bu şərtlərin yerinə yetirilməsini yoxlayaq.

Alqoritmin Tətbiqi

Giriş qrafı qonşuluq siyahısında $g$ saxlanılır. Əks qraf qonşuluq siyahısında $gr$ saxlanılır.

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

dfs1 funksiyası qrafda dərinliklə gəzinti edir.

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

dfs2 funksiyası əks qrafda dərinliklə gəzinti edir.

void dfs2(int v)
{
  used[v] = 1;
  for (int to : gr[v])
    if (!used[to]) dfs2(to);
}

Proqramın əsas hissəsi. Giriş məlumatları oxunur. Əks qraf qurulur.

scanf("%d %d", &n, &m);
g.resize(n + 1);
gr.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  gr[b].push_back(a);
}

Birinci zirvədən başlayaraq ilkin qrafda dərinlik axtarışı aparılır.

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

Əgər $i$ zirvəsinə keçmək mümkün deyilsə (used[i] = 0), o zaman şəhərlər arasında $1$ və $i$ keçidi mümkün deyil.

if (i <= n)
{
  printf("NO\n%d %d\n", 1, i);
  return 0;
}

Birinci zirvədən başlayaraq əks qrafda dərinlik axtarışı aparılır.

used.clear();
used.resize(n + 1);
dfs2(1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) break;

Əgər $i$ zirvəsinə əks qrafda $1$-dən keçmək mümkün deyil (used[i] = 0), o zaman şəhərlər arasında $i$ və $1$ keçidi mümkün deyil.

if (i <= n)
{
  printf("NO\n%d %d\n", i, 1);
  return 0;
}

Qraf güclü şəkildə əlaqəlidir. "YES" mesajını çıxarırıq.

printf("YES\n");