Həll

Gəlin yönləndirilmiş asiklik qrafı (DAG) nəzərdən keçirək. $u$ və $v$ zirvələri üçün belə deyəcəyik: u \prec v, əgər $u$-dan $v$-yə yol varsa. Qrafın istənilən topoloji sıralaması bu münasibəti qoruyan düzülüşdür: əgər u \prec v, onda $u$ mütləq $v$-dən əvvəl dayanmalıdır.

Buradan vacib bir fakt alınır:

• bütün mümkün topoloji sıralamaların çoxluğu tam şəkildə zirvələr arasındakı çatımlılıq (reachability) münasibəti ilə müəyyən olunur;

• əgər bəzi qraf kənarları silindikdən sonra istənilən $u,v$ cütlüyü üçün belə qalırsa: $u$-dan $v$-yə yol var ancaq və ancaq əvvəl də var idisə, onda topoloji sıralamalar çoxluğu dəyişmir.

Deməli, məsələ bizdən əslində DAG-in tranzitiv ixtisarını qurmağı tələb edir: elə minimal kənar çoxluğu saxlayaq ki, hər bir $u,v$ üçün yeganə şərt ödənilsin — yeni qrafda yol var ancaq və ancaq köhnə qrafda var idisə.

Başqa sözlə, $(u,v)$ kənarını o zaman və yalnız o zaman saxlamaq lazımdır ki, $u$-dan $v$-yə uzunluğu $\ge 2$ olan başqa yol olmasın. Əgər belə yol varsa — kənar artıqdır.

Hər bir kənarı ayrıca DFS/BFS ilə yoxlamaq çox yavaşdır, buna görə bunu bütün kənarlar üçün birgə, topoloji sıra və bitmaskalardan istifadə edərək edəcəyik.

1. Topoloji sıra

DFS edirik və zirvəni order massivinə yalnız bütün çıxan kənarları keçəndən sonra əlavə edirik. Onda:

[ u v ;; v əvvəl, u isə sonra düşəcək ]

order massivini çevirməsək, o tərs topoloji sıra kimi qalır: bütün kənarlar “sola” yönəlmiş olur.

pos[x] massivini yaradırıq — burada $x$ zirvəsinin order-də indeksi olur — və yeni qraf $g$ ni qururuq:

[ u v köhnə qrafda pos[u] pos[v] yeni qrafda. ]

Beləcə yeni qrafda bütün kənarlar böyük indeksdən kiçik indeksə yönəlir.

2. 64-lük bloklar və bitmaskalar

Hər zirvə üçün $n$-bitlik bütöv bitset saxlamaq düzgün deyil — çox yaddaş tələb edir. Buna görə zirvələri 64-lük bloklarla emal edirik:

• [i, i+63] indekslərinə malik blok götürürük;

• hər zirvə üçün 64-bitlik dp[v] saxlayırıq: $k$-cı bit $1$-dir, əgər i+k zirvəsi bu blokdan $v$ zirvəsindən çatımlıdırsa.

Cari blok üçün bütün zirvələri v=0,1,\dots,n-1 ardıcıllığı ilə gəzirik. Başlanğıcda:

[ dp[v] =

1 (v - i), v [i, i+63],

[3pt] 0, əks halda.

]

Sonra hər v \to \texttt{to} kənarı üçün:

[ dp[v] |= dp[to]. ]

Bütün kənarlar “soldan sağa yox, sağdan sola” getdiyi üçün hər dp[to] artıq hesablanmış olur. Nəticədə dp[v] $v$-dən blokdakı hansı zirvələrin çatımlı olduğunu göstərir.

—

3. Kənarın vacibliyini necə müəyyən edək?

Hər zirvənin qonşuları g[v] əvvəlcədən azalan sıra ilə sort olunub. İndi belə edirik:

• əgər to cari blokda deyilsə — sadəcə dp[v] |= dp[to] edirik;

• əgər to blokdadırsa, num = to - i olsun — bitin nömrəsi:

  • əgər bu bit artıq dp[v]-də $1$-dirsə, deməli v \to \texttt{to} kənarına alternativ yol var → kənar artıqdır;

  • əgər bit $0$-dırsa — alternativ yol yoxdur → kənar vacibdir.

  Sonra yenə də: [ dp[v] |= dp[to]. ]

Niyə metod bütün artıq kənarları tapır? Yolun ilk zirvəsi p_1 həmişə to-dan böyük indeksə malikdir, biz isə böyük indeksləri əvvəl emal edirik — buna görə alternativ yolun məlumatı dp[v]-yə vaxtında düşür.

Hər kənar yalnız son zirvəsinin daxil olduğu blokda yoxlanılır.

—

4. Cavabın formalaşdırılması

Zirvələri order üzrə yenidən nömrələməyimizə baxmayaraq, çıxışda onların orijinal nömrələri lazımdır. Bunun üçün saxlayırıq:

[ (order[v], order[to]) ]

olan bütün kənarları, sonra sort edib $+1$ əlavə etməklə çap edirik (çünki giriş 1-indekslidir).

Nəticə qrafında:

• hər saxlanılan kənar minimaldır: ucu-ucları arasında başqa yol yoxdur;

• hər silinən kənar tranzitiv idi, yəni başqa yollarla bərpa olunur.

Beləcə çatımlılıq münasibəti və bütün topoloji sıralamalar dəyişmir. Qalan kənarların sayı minimaldır — onlardan heç birini silmək olmaz.

—

5. Mürəkkəblik

$n$ — zirvələrin, $m$ — kənarların sayı olsun.

Təxminən $\lceil n/64\rceil$ blok var. Hər blok üçün bütün zirvələr və bütün kənarlar bir dəfə keçilir → O(n + m).

Ümumi:

[ O((n + m)n64) ]

Bu vaxt və yaddaş məhdudiyyətlərinə uyğundur.

—

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

const int max_n = 1e5 + 11, inf = 1000111222;

using ull = unsigned long long;

vector<int> edge[max_n], g[max_n];
int used[max_n];
vector<int> order;

void dfs (int v) {
    used[v] = 1;
    for (int to : edge[v]) {
        if (!used[to]) dfs(to);
    }
    order.pb(v);
}

ull dp[max_n];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        --a, --b;
        edge[a].pb(b);
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs(i);
    }

    vector<int> pos(n);
    for (int i = 0; i < n; i++) pos[order[i]] = i;

    for (int i = 0; i < n; i++) {
        for (int to : edge[i]) g[pos[i]].pb(pos[to]);
    }
    for (int i = 0; i < n; i++) {
        sort(all(g[i]));
        reverse(all(g[i]));
    }

    vector<pii> ans;
    for (int i = 0; i < n; i += 64) {
        for (int v = 0; v < n; v++) {
            dp[v] = 0;
            if (v >= i && v < i + 64) dp[v] |= 1ull << (v - i);
            for (int to : g[v]) {
                if (to >= i && to < i + 64) {
                    int num = to - i;
                    if (!(dp[v] & (1ull << num))) {
                        ans.pb({order[v], order[to]});
                    }
                }
                dp[v] |= dp[to];
            }
        }
    }

    sort(all(ans));
    cout << len(ans) << '\n';
    for (auto &i : ans) {
        cout << i.first + 1 << ' ' << i.second + 1 << '\n';
    }
}