Просто задача (Розбір)

Розв’язок

Нехай маємо орієнтований ациклічний граф. Для вершин $u$ та $v$ будемо казати, що u \prec v, якщо з $u$ існує шлях у $v$. Будь-яке топологічне впорядкування вершин графа — це лінійний порядок, який поважає це відношення: якщо u \prec v, то $u$ стоїть раніше за $v$.

Звідси важливий факт:

• множина всіх можливих топологічних сортувань цілком визначається відношенням досяжності між вершинами;

• якщо після видалення деяких ребер у графі для будь-яких $u,v$ збереглося: існує шлях з $u$ в $v$ тоді і тільки тоді, коли він існував у початковому графі, — то множина топологічних порядків не зміниться.

Отже задача фактично просить побудувати транзитивне скорочення DAG: залишити мінімальний набір ребер, щоб для кожної пари вершин $u,v$ шлях між ними є в новому графі тоді й лише тоді, коли був у старому.

Іншими словами, ребро $(u,v)$ треба залишити тоді й тільки тоді, коли не існує іншого шляху довжини $\ge 2$ з $u$ в $v$. Якщо такий шлях є, ребро зайве.

Перевіряти кожне ребро окремим пошуком (DFS/BFS) було б надто повільно, тому зробимо це одночасно для всіх ребер, використовуючи топологічний порядок і бітові маски.

1. Топологічний порядок

Зробимо DFS та додаватимемо вершину в масив order після обходу всіх вихідних ребер. Тоді:

[ u v ;; v потрапить у order раніше за u. ]

Якщо не перевертати масив order, то він зберігає обернений топологічний порядок: всі ребра йдуть «вліво».

Побудуємо масив pos, де pos[x] — позиція вершини $x$ в order, і новий граф $g$:

[ u v в початковому графі pos[u] pos[v] в g. ]

Тепер у графі $g$ для кожного ребра індекс початку більший за індекс кінця.

2. Блокування по 64 вершини і бітові маски

Зберігати для кожної вершини повний бітсет розміру $n$ не можна по пам’яті, тому обробляємо вершини блоками по 64:

• розглянемо блок вершин з індексами [i, i+63];

• для кожної вершини $v$ зберігатимемо 64-бітове число dp[v]: $k$-й біт дорівнює $1$, якщо вершина i+k з цього блоку досяжна з вершини $v$.

Для поточного блоку проходимо вершини в порядку зростання індексу v = 0,1,\dots,n-1. На початку для кожної вершини:

[ dp[v] =

1 (v - i), якщо v [i, i+63];

0, інакше.

]

Далі для всіх ребер v \to \texttt{to} виконуємо [ dp[v] |= dp[to]. ]

Оскільки всі ребра йдуть з більшого індексу до меншого, коли ми обробляємо вершину $v$, значення dp[to] для всіх її нащадків уже пораховані. Отже dp[v] зрештою міститиме інформацію, які вершини поточного блоку досяжні з $v$.

3. Як визначити, чи ребро обов’язкове

Для кожної вершини ми заздалегідь відсортували список сусідів g[v] у спадаючому порядку індексів. Тепер, обходячи їх, робимо:

• якщо to не належить поточному блоку, просто оновлюємо dp[v] |= dp[to] і йдемо далі;

• якщо to у поточному блоці, нехай num = to - i — номер біта:

  • якщо біт num уже встановлений у dp[v], це означає, що вже є інший шлях з $v$ до to через сусіда з більшим індексом (бо ми йдемо сусідами у спадаючому порядку). Тоді ребро v \to \texttt{to} зайве;

  • якщо біт ще не встановлений, жодного альтернативного шляху з $v$ у to немає — отже, ребро потрібно залишити в відповіді.

  Після перевірки все одно робимо [ dp[v] |= dp[to]. ]

Чому ми точно знайдемо всі «зайві» ребра? У будь-якому шляху [ v p_1 p_2 ...to ] індекси вершин строго спадають (бо граф ациклічний, а всі ребра йдуть уліво), тому перша вершина p_1 на шляху має індекс більший, ніж у to. Саме такі сусіди ми обробляємо раніше, отже їхня досяжність встигне потрапити в dp[v] до того, як ми дійдемо до ребра v \to \texttt{to}.

Кожне ребро перевіряється рівно в тому блоці, до якого належить його кінцева вершина.

4. Формування відповіді

Працюємо з перенумерованими вершинами (за індексами в order), але у відповідь потрібно вивести початкові номери. Для цього ми зберігаємо пари (order[v], order[to]) для всіх ребер, які вирішили залишити, потім сортуємо їх і виводимо (не забуваючи додати $1$, бо вхід нумерував вершини з одиниці).

У підсумковому графі:

• кожне залишене ребро є мінімальним: між його кінцями немає іншого шляху;

• кожне видалене ребро було транзитивним, тобто його можна відновити через інші ребра.

Отже, відношення досяжності в графі не змінилось, а значить, не змінилася й множина всіх топологічних сортувань. Кількість ребер мінімальна, тому що жодне з тих, що залишилися, вже не можна видалити.

5. Оцінка складності

Нехай $n$ — кількість вершин, $m$ — кількість ребер.

Маємо приблизно $\lceil n/64\rceil$ блоків. Для кожного блока один раз проходимо всі вершини й усі ребра, тобто O(n + m) операцій на блок.

Сумарно отримуємо [ O((n + m)n64) ] операцій, що вкладається в обмеження задачі за часом і пам’яттю.

Нижче наведено реалізацію описаного алгоритму:

//#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;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

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';
    }
}