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