Editorial for Government Promises


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
#include <bits/stdc++.h>
using namespace std;

void dfs(int a, vector<vector<int>> &e, vector<int> &r, vector<int>& v)
{
    if(r[a] >= 0)
        return;
    r[a] = 0;
    v.push_back(a);
    for(auto b : e[a])
        dfs(b, e, r, v);
}

int find(int a, vector<vector<int>> &e, vector<vector<int>> &g, vector<int> &r)
{
    assert(r[a] != 0);
    if(r[a] != -1)
        return r[a];
    vector<int> v;
    dfs(a, e, r, v);
    int res = 0;
    for(auto b : v)
        for(auto c : g[b])
            res = max(res, find(c, e, g, r));
    ++res;
    for(auto b : v)
        r[b] = res;
    return res;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    assert(2 <= n && n <= 1e5);
    assert(2 <= m && m <= 3e5);
    vector<vector<int>> e(n), g(n);
    for(int i = 0; i < m; ++i)
    {
        int a, b;
        string c;
        cin >> a >> b >> c;
        assert(1 <= a && a <= n);
        assert(1 <= b && b <= n);
        assert(a != b);
        assert(c == "=" || c == ">");
        --a;
        --b;
        if(c == "=")
        {
            e[a].push_back(b);
            e[b].push_back(a);
        }
        else
            g[a].push_back(b);
    }
    vector<int> r(n, -1);
    for(int i = 0; i < n; ++i)
        cout << find(i, e, g, r) << ' ';
    cout << endl;
}

int main()
{
    solve();
    return 0;
}