used simple bfs in a grid

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
bool inrange(ll x, ll y, ll n, ll m)
{
    if (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)))
        return true;
    return false;
}
int main()
{
    ll n, m;
    cin >> n >> m;
    vector<string> v(n);
    vector<vector<ll>> vis(n, vector<ll>(m));
    for (auto &i : v)
    {
        cin >> i;
    }
    ll cnt = 0;
    queue<pair<ll, ll>> q;
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < m; j++)
        {
            if (v[i][j] == '#')
                continue;
            if (vis[i][j] == 1)
                continue;

            q.push({i, j});
            vis[i][j] = 1;
            cnt++;
            while (q.size() > 0)
            {
                ll x = q.front().first;
                ll y = q.front().second;
                q.pop();
                for (ll j = 0; j < 4; j++)
                {
                    ll nx = x + dx[j];
                    ll ny = y + dy[j];
                    if ((inrange(nx, ny, n, m) && v[nx][ny] != '#') && vis[nx][ny] == 0)
                    {
                        vis[nx][ny] = 1;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
    cout << cnt;
}

used simple bfs and stored parent for path

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
    return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;

    vector<string> v(n);
    for (auto &i : v)
        cin >> i;
    pair<ll, ll> st;
    pair<ll, ll> endd;
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < m; j++)
        {
            if (v[i][j] == 'A')
            {
                st = {i, j};
            }
            if (v[i][j] == 'B')
            {
                endd = {i, j};
            }
        }
    }
    vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
    vector<vector<ll>> vis(n, vector<ll>(m, 0));
    vis[st.first][st.second] = 1;
    queue<pair<ll, ll>> q;
    q.push(st);
    while (q.size())
    {
        ll x = q.front().first;
        ll y = q.front().second;
        q.pop();
        for (ll j = 0; j < 4; j++)
        {
            ll nx = x + dx[j];
            ll ny = y + dy[j];
            if (!(inrange(nx, ny, n, m)))
                continue;
            if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
            {
                prev[nx][ny] = {x, y};
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    if (vis[endd.first][endd.second] == 0)
    {
        cout << "NO\n";
        return 0;
    }
    vector<pair<ll, ll>> res;
    // res.push_back(endd);
    pair<ll, ll> curr = endd;
    while (curr != st)
    {
        res.push_back(curr);
        curr = {prev[curr.first][curr.second]};
    }
    res.push_back(st);

    reverse(res.begin(), res.end());
    // for(auto i: res)
    // {
    //     cout<<i.first<<" "<<i.second<<"\n";
    // }
    cout << "YES\n";
    cout << res.size() - 1 << "\n";
    string direc = "";
    for (ll i = 0; i < (ll)(res.size() - 1); i++)
    {
        if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
        {
            direc += 'D';
        }
        else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
        {
            direc += 'R';
        }
        else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
        {
            direc += 'U';
        }
        else
        {
            direc += 'L';
        }
    }
    cout << direc << "\n";
}

do bfs and store the starting vertex of each bfs traversal

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll t = 1;
    // cin>>t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<vector<ll>> v(n);
        for (ll i = 0; i < m; i++)
        {
            ll x, y;
            cin >> x >> y;
            x--;
            y--;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        vector<ll> vis(n, 0);
        vector<ll> heads;
        for (ll i = 0; i < n; i++)
        {
            if (vis[i] == 1)
                continue;
            heads.push_back(i);
            queue<ll> q;
            q.push(i);
            vis[i] = 1;
            while (q.size())
            {
                ll curr = q.front();
                q.pop();
                for (auto child : v[curr])
                {
                    if (vis[child] == 1)
                        continue;
                    vis[child] = 1;
                    q.push(child);
                }
            }
        }
        // for(auto i: heads)
        // {
        //     cout<<i<<" ";
        // }
        cout << heads.size() - 1 << "\n";
        for (ll i = 0; i < ((ll)(heads.size() - 1)); i++)
        {
            cout << heads[i] + 1 << " " << heads[i + 1] + 1 << "\n";
        }
    }
}

do bfs and store parent

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll t = 1;
    // cin>>t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<vector<ll>> v(n);
        while (m--)
        {
            ll x, y;
            cin >> x >> y;
            x--;
            y--;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        vector<ll> vis(n, 0);
        queue<ll> q;
        q.push(0);
        vis[0] = 1;
        vector<ll> prev(n, -1);
        while (q.size())
        {
            ll curr = q.front();
            q.pop();
            for (auto child : v[curr])
            {
                if (vis[child] == 1)
                    continue;
                q.push(child);
                vis[child] = 1;
                prev[child] = curr;
            }
        }
        if (vis[n - 1] == 0)
        {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        vector<ll> res;
        ll cur = n - 1;
        // res.push_back();
        while (cur != 0)
        {
            res.push_back(cur);
            cur = prev[cur];
        }
        res.push_back(cur);
        reverse(res.begin(), res.end());
        cout << res.size() << "\n";
        for (auto i : res)
            cout << i + 1 << " ";
    }
}

check if the graph can be divided into a bipartite graph using bfs.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
vector<vector<ll>> adj(100001);
vector<ll> vis(100001, 0);
vector<ll> team(100001, 0);
bool dfs(ll node, ll ct)
{
    vis[node] = 1;
    team[node] = ct;
    for (auto &i : adj[node])
    {
        if (team[i] == 0)
        {
            bool temp = dfs(i, 3 - ct);
            if (temp == false)
                return false;
        }
        else if (team[i] == ct)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    fastio;
    ll t = 1;
    // cin>>t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        while (m--)
        {
            ll x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        bool ans = true;
        for (ll i = 1; i <= n; i++)
        {
            if (vis[i])
                continue;
            ll res = dfs(i, 1);
            if (!res)
            {
                ans = false;
                break;
            }
        }
        if (ans)
        {
            for (ll i = 1; i <= n; i++)
                cout << team[i] << " ";
        }
        else
            cout << "IMPOSSIBLE\n";
    }
}

use graph coloring to detect and print cycle by storing parent for each node.. as soon as cycle is detected ,.. print cycle and end program

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll paret[100005];
ll colour[100005];
ll vis[100005];
vector<vector<ll>> adj(100005);
bool dfs(int node, int parent)
{
    vis[node] = 1;
    paret[node] = parent;
    colour[node] = 1;
    for (auto child : adj[node])
    {
        if (child != parent && colour[child] == 1)
        {
            vector<ll> res;
            ll x = node;
            while (x != child)
            {
                res.push_back(x);
                x = paret[x];
            }
            res.push_back(x);
            // if(res[0]==res[res.size()-1])
            // res.pop_back();
            res.push_back(res[0]);
            cout << res.size() << "\n";
            for (auto x : res)
                cout << x << " ";
            exit(0);
            return true;
        }
        else if (child != parent && colour[child] == 0)
        {
            bool temp = dfs(child, node);
            if (temp == true)
            {
                vector<ll> res;
                ll x = paret[child];
                while (paret[x] != child)
                {
                    res.push_back(x);
                    x = paret[x];
                }
                cout << res.size() << "\n";
                for (auto x : res)
                    cout << x << " ";
                exit(0);
                return true;
            }
        }
    }
    colour[node] = 2;
    return false;
}

int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    while (m--)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] == 1)
        {
            continue;
        }
        // memset(colour,0,sizeof colour);
        dfs(i, 0);
    }
    cout << "IMPOSSIBLE\n";
}

places where the monsters can reach before the person, can be considered to be as good as blocked,so first run a multisource bfs with all the monsters to find the time taken to reach all non blocked cells by the monsters then run a bfs using the persons position to find the time taken by the person to reach there finally if there is any boundary cell such that the person can reach it before the monsters,.. then print the path to it otherwise print impossible

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
bool issafe(ll x, ll y, ll n, ll m)
{
    return ((0 <= x) && (x < n)) && ((0 <= y) && (y < m));
}
char pro(pair<ll, ll> a, pair<ll, ll> b)
{
    if ((a.second + 1) == (b.second))
    {
        return 'R';
    }
    else if ((a.second - 1) == (b.second))
    {
        return 'L';
    }
    else if ((a.first - 1) == (b.first))
    {
        return 'U';
    }
    else
        return 'D';
}
int main()
{
    fastio;
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<string> v(n);
        for (auto &i : v)
            cin >> i;
        queue<pair<ll, ll>> q;
        vector<vector<ll>> dist(n, vector<ll>(m, LLONG_MAX));
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        for (ll i = 0; i < n; i++)
        {
            for (ll j = 0; j < m; j++)
            {
                if (v[i][j] == 'M')
                {
                    q.push({i, j});
                    dist[i][j] = 0;
                    vis[i][j] = true;
                }
            }
        }
        while (q.size() > 0)
        {
            auto z = q.front();
            ll x = z.first;
            ll y = z.second;
            q.pop();
            for (ll i = 0; i < 4; i++)
            {
                ll nx = x + dx[i];
                ll ny = y + dy[i];
                if ((issafe(nx, ny, n, m) && (v[nx][ny] != '#')) && (!vis[nx][ny]))
                {
                    dist[nx][ny] = dist[x][y] + 1;
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        vector<vector<ll>> dista(n, vector<ll>(m, LLONG_MAX));
        vector<vector<bool>> vista(n, vector<bool>(m, false));
        queue<pair<ll, ll>> qa;
        map<pair<ll, ll>, pair<ll, ll>> par;
        for (ll i = 0; i < n; i++)
        {
            for (ll j = 0; j < m; j++)
            {
                if (v[i][j] == 'A')
                {
                    qa.push({i, j});
                    dista[i][j] = 0;
                    vista[i][j] = true;
                    par[{i, j}] = {i, j};
                }
            }
        }
        while (qa.size() > 0)
        {
            auto z = qa.front();
            ll x = z.first;
            ll y = z.second;
            qa.pop();
            for (ll i = 0; i < 4; i++)
            {
                ll nx = x + dx[i];
                ll ny = y + dy[i];
                if (((issafe(nx, ny, n, m) && v[nx][ny] != '#')) && (!vista[nx][ny]))
                {
                    dista[nx][ny] = dista[x][y] + 1;
                    vista[nx][ny] = true;
                    qa.push({nx, ny});
                    par[{nx, ny}] = {x, y};
                }
            }
        }
        vector<pair<ll, ll>> res;
        bool f = true;
        for (ll i = 0; i < n; i++)
        {
            for (ll j = 0; j < m; j++)
            {
                if (((i == 0) || (j == 0)) || ((i == n - 1) || (j == m - 1)))
                {
                    if (dista[i][j] < dist[i][j])
                    {
                        pair<ll, ll> z = {i, j};
                        while (par[z] != z)
                        {
                            res.push_back(z);
                            z = par[z];
                        }
                        res.push_back(z);
                        f = false;
                        break;
                    }
                }
            }
            if (!f)
            {
                break;
            }
        }
        // for (auto &i : res)
        // {
        //     cout << i.first << " " << i.second << "\n";
        // }
        if (!f)
        {
            cout << "YES\n";
            ll x = res.size();
            cout << x - 1 << "\n";
            reverse(res.begin(), res.end());
            for (ll i = 0; i < x - 1; i++)
            {
                char ch = pro(res[i], res[i + 1]);
                cout << ch;
            }
        }
        else
        {
            cout << "NO\n";
        }
        // for (auto &i : dist)
        // {
        //     for (auto &j : i)
        //     {
        //         cout << j << " ";
        //     }
        //     cout << "\n";
        // }
    }
}

simple djikstra

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll t = 1;
    // cin/>>t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<vector<pair<ll, ll>>> adj(n + 1);
        vector<ll> dist(n + 1, LLONG_MAX);
        dist[1] = 0;
        while (m--)
        {
            ll u, v, w;
            cin >> u >> v >> w;
            adj[u].push_back({v, w});
        }
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        pq.push({0, 1});
        while (pq.size())
        {
            ll distance = pq.top().first;
            ll node = pq.top().second;
            pq.pop();
            if (distance > dist[node])
                continue;
            for (auto &child : adj[node])
            {
                if (dist[child.first] > distance + (child.second))
                {
                    dist[child.first] = distance + (child.second);
                    pq.push({distance + (child.second), child.first});
                }
            }
        }
        for (ll i = 1; i <= n; i++)
            cout << dist[i] << " ";
    }
}

simple Floyd Warshall

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll t = 1;
    // cin/>>t;
    while (t--)
    {
        ll n, m, q;
        cin >> n >> m >> q;
        vector<vector<pair<ll, ll>>> adj(n + 1);
        // vector<ll> dist(n+1,LLONG_MAX);
        // dist[1] = 0;
        vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, LLONG_MAX));
        while (m--)
        {
            ll u, v, w;
            cin >> u >> v >> w;
            dist[u][v] = min(dist[u][v], w);
            dist[v][u] = min(dist[v][u], w);
        }
        for (ll i = 1; i <= n; i++)
            dist[i][i] = 0;
        for (ll k = 1; k <= n; k++)
        {
            for (ll i = 1; i <= n; i++)
            {
                for (ll j = 1; j <= n; j++)
                {
                    if ((dist[i][k] != LLONG_MAX) && (dist[k][j] != LLONG_MAX))
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        while (q--)
        {
            ll x, y;
            cin >> x >> y;
            cout << ((dist[x][y] == LLONG_MAX) ? -1 : dist[x][y]) << "\n";
        }
        // for(ll i=1;i<=n;i++)
        // cout<<dist[i]<<" ";
    }
}

negate the edge weights and use bellman ford to get the minimum negative score ,.. i.e. the max score in positive numbers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
vector<ll> vis(2501, 0);
void dfs(ll node, ll parent, vector<ll> &reachable, vector<vector<ll>> &adjrev)
{
    if (vis[node] == 1)
    {
        return;
    }
    else
    {
        reachable.push_back(node);
        vis[node] = 1;
        for (auto &i : adjrev[node])
        {
            if (i == parent)
                continue;
            dfs(i, node, reachable, adjrev);
        }
    }
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> adj(n + 1);
    vector<pair<pair<ll, ll>, ll>> edges;
    for (ll i = 0; i < m; i++)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        edges.push_back({{u, v}, -w});
        adj[u].push_back({v, -w});
    }
    vector<ll> dist(n + 1, LLONG_MAX);
    dist[1] = 0;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 0; j < m; j++)
        {
            ll u = edges[j].first.first;
            ll v = edges[j].first.second;
            ll w = edges[j].second;
            if (dist[u] != LLONG_MAX)
            {
                dist[v] = min(dist[v], dist[u] + w);
            }
        }
    }
    // bool f = true;
    ll x = dist[n];
    set<ll> temp;
    for (ll j = 0; j < m; j++)
    {
        ll u = edges[j].first.first;
        ll v = edges[j].first.second;
        ll w = edges[j].second;
        if (dist[u] != LLONG_MAX)
        {
            ll x = dist[v];
            dist[v] = min(dist[v], dist[u] + w);
            if (x != dist[v])
                temp.insert(v);
        }
    }
    for (auto &i : edges)
    {
        swap(i.first.first, i.first.second);
    }
    vector<vector<ll>> adjrev(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll u = edges[i].first.first;
        ll v = edges[i].first.second;
        adjrev[u].push_back(v);
    }
    vector<ll> reachable;
    dfs(n, -1, reachable, adjrev);
    bool f = true;
    for (auto &i : reachable)
    {
        if (temp.find(i) != temp.end())
        {
            f = false;
            break;
        }
    }

    // if (x != dist[n])
    // {
    //     f = false;
    // }
    if (f)
        cout << -dist[n] << "\n";
    else
        cout << "-1\n";
}

use state djikstra What is state djikstra you might ask:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> adj(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // adj[v].push_back({u, w});
    }
    priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;
    vector<vector<ll>> dis(n + 1, vector<ll>(2, LLONG_MAX));
    dis[1][0] = 0;
    dis[1][1] = 0;
    pq.push({0, 1, 1});
    while (pq.size() > 0)
    {
        auto z = pq.top();
        pq.pop();
        ll dist = z[0];
        ll node = z[1];
        ll available = z[2];
        if (dis[node][available] < dist)
            continue;
        for (auto &ch : adj[node])
        {
            if (available == 1)
            {
                if (dis[ch.first][1] > (dist + ch.second))
                {
                    dis[ch.first][1] = dist + ch.second;
                    pq.push({dis[ch.first][1], ch.first, 1});
                }
                if (dis[ch.first][0] > (dist + (ch.second) / 2))
                {
                    dis[ch.first][0] = (dist + (ch.second) / 2);
                    pq.push({dis[ch.first][0], ch.first, 0});
                }
            }
            else
            {
                if (dis[ch.first][0] > (dist + (ch.second)))
                {
                    dis[ch.first][0] = (dist + (ch.second));
                    pq.push({dis[ch.first][0], ch.first, 0});
                }
            }
        }
    }
    cout << min(dis[n][0], dis[n][1]) << "\n";
}

use bellman ford to detect the presence of a negative cycle,.. Now, to print it,.. run bellman ford again(keep track of parent of nodes),... now,.. take any node whose value gets updated and keep on visiting its parent until the node itself is found,.. and u have found ur cycle .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> adj(n + 1);
    vector<vector<ll>> edges;
    for (ll i = 0; i < m; i++)
    {
        ll x, y, w;
        cin >> x >> y >> w;
        adj[x].push_back({y, w});
        edges.push_back({x, y, w});
    }
    vector<ll> dist(n + 1, 0);
    dist[1] = 0;
    for (ll i = 0; i < n; i++)
    {
        for (auto &edge : edges)
        {
            ll u = edge[0];
            ll v = edge[1];
            ll w = edge[2];
            if (dist[u] != LLONG_MAX)
            {
                dist[v] = min(dist[v], dist[u] + w);
            }
        }
    }
    bool f = true;
    vector<ll> par(n + 1, -1);
    for (ll i = 0; i < n; i++)
    {
        for (auto &edge : edges)
        {
            ll u = edge[0];
            ll v = edge[1];
            ll w = edge[2];
            if (dist[u] != LLONG_MAX)
            {
                // if (dist[v] > dist[u] + w)
                // {
                ll z = dist[v];
                dist[v] = min(dist[v], dist[u] + w);
                if (dist[v] != z)
                {
                    f = false;
                    par[v] = u;
                }
                // }
            }
        }
    }
    if (f)
    {
        cout << "NO\n";
    }
    else
    {
        ll x = 0;
        for (ll i = 1; i <= n; i++)
        {
            if (par[i] != -1)
            {
                x = i;
                break;
            }
        }
        vector<ll> cycle;
        unordered_set<ll> st;
        while (st.find(x) == st.end())
        {
            cycle.push_back(x);
            st.insert(x);
            x = par[x];
        }
        cycle.push_back(x);
        reverse(cycle.begin(), cycle.end());
        cout << "YES\n";
        unordered_set<ll> final;
        for (auto &i : cycle)
        {
            cout << i << " ";
            if (final.find(i) != final.end())
            {
                break;
            }
            final.insert(i);
        }
    }
}

Do djikstra,.. and keep track of all the distances...in a max heap.. if the size of the maxheap for the nth node is greater than n,.. then pop the largest element and insert the current distance if it is smaller than the top of the max heap

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    fastio;
    int n, m, k;
    cin >> n >> m >> k;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    priority_queue<ll> bes[n + 1];
    vector<pair<ll, ll>> adj[n + 1];
    for (ll i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    bes[1].push(0);
    pq.push({0, 1});
    while (pq.size() > 0)
    {
        auto a = pq.top();
        pq.pop();
        if (a.first > bes[a.second].top())
            continue;
        for (auto &i : adj[a.second])
        {
            ll tmp = a.first + i.second;
            if (bes[i.first].size() < k)
            {
                bes[i.first].push(tmp);
                pq.push({tmp, i.first});
            }
            else if (tmp < bes[i.first].top())
            {
                bes[i.first].pop();
                bes[i.first].push(tmp);
                pq.push({tmp, i.first});
            }
        }
    }
    vector<ll> ans;
    while (bes[n].size() > 0)
    {
        ans.push_back(bes[n].top());
        bes[n].pop();
    }
    reverse(ans.begin(), ans.end());
    for (auto a : ans)
        cout << a << " ";
}

same as round trip,..except here the graph is directed

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll paret[100005];
ll colour[100005];
ll vis[100005];
vector<vector<ll>> adj(100005);
bool dfs(int node, int parent)
{
    vis[node] = 1;
    paret[node] = parent;
    colour[node] = 1;
    for (auto child : adj[node])
    {
        if (colour[child] == 1)
        {
            vector<ll> res;
            ll x = node;
            while (x != child)
            {
                res.push_back(x);
                x = paret[x];
            }
            res.push_back(x);
            // if(res[0]==res[res.size()-1])
            // res.pop_back();
            res.push_back(res[0]);
            cout << res.size() << "\n";
            reverse(res.begin(), res.end());
            for (auto x : res)
                cout << x << " ";
            exit(0);
            return true;
        }
        else if (colour[child] == 0)
        {
            bool temp = dfs(child, node);
            if (temp == true)
            {
                vector<ll> res;
                ll x = paret[child];
                while (paret[x] != child)
                {
                    res.push_back(x);
                    x = paret[x];
                }
                cout << res.size() << "\n";
                reverse(res.begin(), res.end());
                for (auto x : res)
                    cout << x << " ";
                exit(0);
                return true;
            }
        }
    }
    colour[node] = 2;
    return false;
}

int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;

    while (m--)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        // adj[y].push_back(x);
    }
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] == 1)
        {
            continue;
        }
        // memset(colour,0,sizeof colour);
        dfs(i, 0);
    }
    cout << "IMPOSSIBLE\n";
}

topological sort using vertex removal algorithm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool comp(const pair<ll, ld> &a, const pair<ll, ld> &b)
{
}
int main()
{
    fastio;
    ll t = 1;
    // cin>>t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<vector<ll>> adj(n + 1);
        vector<ll> in_degree(n + 1, 0);
        for (ll i = 0; i < m; i++)
        {
            ll x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            in_degree[y]++;
        }
        queue<ll> q;
        for (ll i = 1; i < n + 1; i++)
        {
            if (in_degree[i] == 0)
            {
                q.push(i);
            }
        }
        vector<ll> topo_sort;
        while (q.size())
        {
            ll x = q.front();
            q.pop();
            topo_sort.push_back(x);
            bool f = true;
            for (auto &i : adj[x])
            {
                in_degree[i]--;
                if (in_degree[i] == 0)
                {
                    q.push(i);
                    f = false;
                }
            }
            // if(f)
            // {
            //     cout<<"IMPOSSIBLE\n";
            //     exit(0);
            // }
        }
        if (topo_sort.size() == n)
        {

            for (auto i : topo_sort)
            {
                cout << i << " ";
            }
        }
        else
        {
            cout << "IMPOSSIBLE\n";
        }
    }
}

it is given that the graph is a DAG(Directed acyclic graph),.. so we can use DP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
vector<ll> dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<vector<ll>> &dp)
{
    if (node == dest)
    {
        return {1, -1, 1};
    }
    if (!(((dp[node][0] == -1) && (dp[node][1] == -1)) && (dp[node][2] == -1)))
    {
        return dp[node];
    }
    ll f = 0;
    ll dist = 0;
    ll nextcity = -1;
    for (auto &i : adj[node])
    {
        vector<ll> z = dfs(i, dest, adj, dp);
        if (z[2] == 1)
        {
            f = 1;
            if (dist < z[0])
            {
                dist = z[0];
                nextcity = i;
            }
        }
    }
    return (dp[node] = {dist + 1, nextcity, f});
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(3, -1));
    ll x = 1;
    if (dfs(1, n, adj, dp)[2] != 1)
    {
        cout << "IMPOSSIBLE\n";
    }
    else
    {
        cout << dfs(1, n, adj, dp)[0] << "\n";
        ll x = 1;
        while (dfs(x, n, adj, dp)[1] != -1)
        {
            cout << x << " ";
            x = dfs(x, n, adj, dp)[1];
        }
        cout << x << "\n";
    }
}

again its a DAG,.. so we use dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll mod = (ll)(1e9 + 7);
pair<ll, ll> dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<pair<ll, ll>> &dp) // ways,possibel
{
    if (node == dest)
    {
        return {1, 1};
    }
    if (!((dp[node].first == -1) && (dp[node].second == -1)))
    {
        return dp[node];
    }
    ll ways = 0;
    ll f = 0;
    for (auto &i : adj[node])
    {
        auto z = dfs(i, dest, adj, dp);
        if (z.second == 1)
        {
            f = 1;
            ways += z.first;
            ways %= mod;
        }
    }
    return (dp[node] = {ways, f});
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }
    vector<pair<ll, ll>> dp(n + 1, {-1, -1});
    auto z = dfs(1, n, adj, dp);
    cout << z.first << "\n";
}

state djikstra for each node,.. maintain the given four states: dist,ways,minc,maxc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll mod = (ll)(1e9 + 7);
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> adj(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    // vector<pair<ll, ll>> dist(n + 1, {LLONG_MAX, 0}); // dist,ways
    vector<ll> dist(n + 1, LLONG_MAX);
    vector<ll> ways(n + 1, 0);
    vector<ll> minc(n + 1, 0);
    vector<ll> maxc(n + 1, 0);
    dist[1] = 0;
    ways[1] = 1;
    minc[1] = 1;
    maxc[1] = 1;
    pq.push({0, 1});
    while (pq.size() > 0)
    {
        auto z = pq.top();
        pq.pop();
        ll u = z.second;
        ll w = z.first;
        if (dist[u] < w)
        {
            continue;
        }
        for (auto &i : adj[u])
        {
            ll v = i.first;
            ll weight = i.second;
            if (dist[v] > w + weight)
            {
                dist[v] = w + weight;
                ways[v] = ways[u];
                minc[v] = minc[u] + 1;
                maxc[v] = maxc[u] + 1;
                pq.push({dist[v], v});
            }
            else if (dist[v] == (w + weight))
            {
                // dist[v] = w + weight;
                ways[v] += ways[u];
                ways[v] %= mod;
                minc[v] = min(minc[v], minc[u] + 1);
                maxc[v] = max(maxc[v], maxc[u] + 1);
            }
        }
    }
    cout << dist[n] << " " << ways[n] << " " << minc[n] - 1 << " " << maxc[n] - 1 << "\n";
}

use binary jumping i.e. for each node calculate findpar(x,k).. i.e. the 2^k th successor of node x. Now if we need to find the dth successor of the xth node, represent d as the sum of powers of 2. This is similar to binary lifting used to find the kth ancestor of a node in a tree.

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll n, q;
// vector<vector<ll>> dp(2e5 + 1, vector<ll>(30, -1));
ll dp[200001][30];
ll findpar(ll node, ll k)
{
    ll x = node;
    for (ll i = 0; i < 30; i++)
    {
        if (k & (1ll << i))
        {
            // x = f(x, i, dp, par);
            x = dp[x][i];
        }
    }
    return x;
}
int main()
{
    fastio;
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
    {
        cin >> dp[i][0];
    }
    for (ll i = 1; i < 30; i++)
    {
        for (ll j = 1; j <= n; j++)
        {
            dp[j][i] = dp[dp[j][i - 1]][i - 1];
        }
    }
    while (q--)
    {
        ll a, b;
        cin >> a >> b;
        cout << findpar(a, b) << "\n";
    }
}

This is a successor graph,.. so it can be divided into components having a cycle and a paths pointing to the cycle so if the nodes belong to the same cycle,.. then the distance is (dfs number(v)-dfs number(u)+cyclelength)%cyclelength else if both are not part of any cycle,.. then if we jump from u by (dfs number(v)-dfs number(v)), and we reach v,.. then the answer is jump else its -1 now if one node is in a cycle and the other isnt then the one outside the cycle,.. we find the nearest cycle node to it using binary jumping and binary search let this closest cycle node be called interm(as in intermediate node) now dist = distance between u and interm + distance between interm and y(can be found using (dfs number(y)-dfs number(interm)+cyclelength)%cyclelength.. as shown int the above case)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void addno(ll i, unordered_set<ll> &done, vector<ll> &nextnode, vector<ll> &no)
{
    if (done.find(i) != done.end())
        return;
    addno(nextnode[i], done, nextnode, no);
    done.insert(i);
    no[i] = no[nextnode[i]] - 1;
}
ll dp[200005][30];
ll findpar(ll node, ll k)
{
    ll x = node;
    for (ll i = 0; i < 30; i++)
    {
        if (k & (1ll << i))
        {
            // x = f(x, i, dp, par);
            x = dp[x][i];
        }
    }
    return x;
}
int main()
{
    fastio;
    ll n, q;
    cin >> n >> q;
    vector<ll> nextnode(n + 1);
    for (ll i = 1; i <= n; i++)
    {
        cin >> nextnode[i];
        dp[i][0] = nextnode[i];
    }
    vector<ll> vis(n + 1, 0);
    for (ll i = 1; i < 30; i++)
    {
        for (ll j = 1; j <= n; j++)
        {
            dp[j][i] = dp[dp[j][i - 1]][i - 1];
        }
    }
    // vector<ll> answer(n + 1, -1);
    vector<vector<ll>> cycles;
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            unordered_set<ll> tempset;
            vector<ll> tempvec;
            ll x = i;
            bool flag = true;
            while (tempset.find(x) == tempset.end())
            {
                tempset.insert(x);
                tempvec.push_back(x);
                if (vis[x])
                {
                    flag = false;
                    break;
                }
                x = nextnode[x];
            }
            if (!flag)
            {
                for (auto &i : tempvec)
                    vis[i] = 1;
                continue;
            }
            ll z = find(tempvec.begin(), tempvec.end(), x) - tempvec.begin();
            ll m = tempvec.size();
            vector<ll> cycle;
            for (ll i = z; i < m; i++)
            {
                vis[tempvec[i]] = 1;
                cycle.push_back(tempvec[i]);
            }
            for (ll i = z - 1; i >= 0; i--)
            {
                vis[tempvec[i]] = 1;
            }
            cycles.push_back(cycle);
        }
    }
    vector<ll> no(n + 1, -1);
    unordered_set<ll> done;
    vector<ll> cycleidx(n + 1, -1);
    ll idx = 0;
    for (auto &i : cycles)
    {
        ll c = 0;
        for (auto &j : i)
        {
            no[j] = c++;
            cycleidx[j] = idx;
            done.insert(j);
        }
        idx++;
    }
    for (ll i = 1; i <= n; i++)
    {
        addno(i, done, nextnode, no);
    }
    // for (ll i = 1; i <= n; i++)
    //     cout << cycleidx[i] << " " << no[i] << "\n";
    while (q--)
    {
        ll x, y;
        cin >> x >> y;
        if ((cycleidx[x] == cycleidx[y]) && ((cycleidx[x] != -1) && (cycleidx[y] != -1)))
        {
            ll b = cycles[cycleidx[x]].size();
            cout << ((no[y] - no[x] + b) % b) << "\n";
        }
        else if ((cycleidx[x] == -1) || (cycleidx[y] == -1))
        {
            if ((cycleidx[x] == -1) && (cycleidx[y] == -1))
            {
                if (no[x] > no[y])
                    cout << "-1\n";
                else
                {
                    ll jump = no[y] - no[x];
                    if (findpar(x, jump) == y)
                        cout << jump << "\n";
                    else
                        cout << "-1\n";
                }
            }
            else
            {
                // if (no[x] > no[y])
                // {
                if ((cycleidx[x] != -1) && (cycleidx[y] == -1))
                    cout << "-1\n";
                else
                {
                    ll lo = 0;
                    ll hi = n;
                    ll ans = -1;
                    while (lo <= hi)
                    {
                        ll mid = (lo + hi) / 2;
                        if (cycleidx[findpar(x, mid)] != -1)
                        {
                            ans = mid;
                            hi = mid - 1;
                        }
                        else
                        {
                            lo = mid + 1;
                        }
                    }
                    ll interm = findpar(x, ans);
                    if (cycleidx[interm] == cycleidx[y])
                    {
                        ll h = cycles[cycleidx[y]].size();
                        cout << ((no[interm] - no[x]) + ((no[y] - no[interm] + h) % h)) << "\n";
                    }
                    else
                    {
                        cout << "-1\n";
                    }
                }
            }
        }
        else
        {
            cout << "-1\n";
        }
    }
}

this is again a successor graph,.. so we divide it into components having a cycle and paths pointing to the cycles,.. so we do dfs,.. and keep track of the dfs numbers for each node in the cycle,.. the answer is the cycle length.. for other nodes,.. let the node be x,..ans[x] = ans[nextnode[x]]+1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll n;
    cin >> n;
    vector<ll> nextnode(n + 1);
    for (ll i = 1; i <= n + 1; i++)
    {
        cin >> nextnode[i];
    }
    vector<ll> vis(n + 1, 0);
    vector<ll> answer(n + 1, -1);
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            unordered_set<ll> tempset;
            vector<ll> tempvec;
            ll x = i;
            bool flag = true;
            while (tempset.find(x) == tempset.end())
            {
                tempset.insert(x);
                tempvec.push_back(x);
                if (vis[x])
                {
                    flag = false;
                    break;
                }
                x = nextnode[x];
            }
            ll z = find(tempvec.begin(), tempvec.end(), x) - tempvec.begin();
            ll m = tempvec.size();
            for (ll i = z; i < m; i++)
            {
                vis[tempvec[i]] = 1;
                if (answer[tempvec[i]] == -1)
                    answer[tempvec[i]] = m - z;
            }
            for (ll i = z - 1; i >= 0; i--)
            {
                vis[tempvec[i]] = 1;
                if (answer[tempvec[i]] == -1)
                    answer[tempvec[i]] = answer[tempvec[i + 1]] + 1;
            }
        }
    }
    for (ll i = 1; i <= n; i++)
        cout << answer[i] << " ";
}

simple MST finding,.. I have implemented using kruskals algo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
vector<ll> ranq(100001);
vector<ll> par(100001);
void make_set(ll n)
{
    for (ll i = 1; i <= n; i++)
    {
        ranq[i] = 1;
        par[i] = i;
    }
}
ll find_set(ll x)
{
    if (par[x] == x)
    {
        return x;
    }
    par[x] = find_set(par[x]);
    return par[x];
}
void union_set(ll a, ll b)
{
    ll x = find_set(a);
    ll y = find_set(b);
    if (x == y)
        return;
    if (ranq[x] > ranq[y])
    {
        par[y] = x;
        ranq[x] += ranq[y];
    }
    else
    {
        par[x] = y;
        ranq[y] += ranq[x];
    }
}
int32_t main()
{
    fastio;
    ll t = 1;
    // cin>>t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        make_set(n);
        vector<pair<ll, pair<ll, ll>>> v;
        while (m--)
        {
            ll a, b, c;
            cin >> a >> b >> c;
            v.push_back({c, {a, b}});
        }
        sort(v.begin(), v.end());
        m = v.size();
        ll cost = 0;
        for (ll i = 0; i < m; i++)
        {
            ll x = v[i].second.first;
            ll y = v[i].second.second;
            ll w = v[i].first;
            if (find_set(x) != find_set(y))
            {
                cost += w;
                union_set(x, y);
            }
        }
        if (ranq[find_set(1)] == n)
        {
            cout << cost << "\n";
        }
        else
        {
            cout << "IMPOSSIBLE\n";
        }
    }
}

we use dsu,.. while merging two nodes,if their parents were same,.. we return false,.. otherwise return true hence if two nodes were merged whose parents were different,.. then we can see that the number of components decreases otherwise if theri parents are same,.. it remains unchanged

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll maxcomp = 1;
vector<ll> ranq(100001);
vector<ll> par(100001);
void make_set(ll n)
{
    for (ll i = 1; i <= n; i++)
    {
        ranq[i] = 1;
        par[i] = i;
    }
}
ll find_set(ll x)
{
    if (x == par[x])
        return x;
    par[x] = find_set(par[x]);
    return par[x];
}
bool union_set(ll a, ll b)
{
    ll x = find_set(a);
    ll y = find_set(b);
    if (x == y)
        return false;
    if (ranq[x] > ranq[y])
    {
        par[y] = x;
        ranq[x] += ranq[y];
        if (ranq[x] > maxcomp)
        {
            maxcomp = ranq[x];
        }
        return true;
    }
    else
    {
        par[x] = y;
        ranq[y] += ranq[x];
        if (ranq[y] > maxcomp)
        {
            maxcomp = ranq[y];
        }
        return true;
    }
}
int32_t main()
{
    fastio;
    ll t = 1;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        make_set(n);
        ll nocomp = n;
        while (m--)
        {
            ll x, y;
            cin >> x >> y;
            bool res = union_set(x, y);
            if (res)
            {
                nocomp--;
            }
            cout << nocomp << " " << maxcomp << "\n";
        }
    }
}

the question reduces itself to the simple problem of checking if the entire graph is a single stringly connected component or not we apply kosaraju's algorithm to find sccs for each scc ,.. we store the head node i.e. while doing the second dfs in the decreasing order of finish times if there are 2 or more sccs,.. we print head nodes of the first 2 SCCs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &finish, ll &timer, vector<ll> &vis)
{
    vis[node] = 1;
    for (auto &i : adj[node])
    {
        if (vis[i] == 0)
        {
            dfs(i, adj, finish, timer, vis);
        }
    }
    finish[node] = timer++;
}
void dfs2(ll node, vector<ll> &vis, vector<vector<ll>> &adj)
{
    vis[node] = 1;
    for (auto &i : adj[node])
    {
        if (vis[i] == 0)
        {
            dfs2(i, vis, adj);
        }
    }
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1);
    vector<vector<ll>> adjt(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adjt[y].push_back(x);
    }
    vector<ll> finish(n + 1, -1);
    vector<ll> vis(n + 1, 0);
    ll timer = 0;
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            dfs(i, adj, finish, timer, vis);
        }
    }
    vector<ll> ord(n);
    for (ll i = 0; i < n; i++)
    {
        ord[i] = i + 1;
    }
    sort(ord.begin(), ord.end(), [&](ll a, ll b)
         { return (finish[a] > finish[b]); });
    vis.clear();
    vis.resize(n + 1, 0);
    ll cnt = 0;
    vector<ll> nodes;
    for (ll i = 0; i < n; i++)
    {
        if (vis[ord[i]] == 0)
        {
            nodes.push_back(ord[i]);
            cnt++;
            dfs2(ord[i], vis, adjt);
        }
    }
    if (cnt == 1)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
        cout << nodes[1] << " " << nodes[0] << "\n";
    }
}

we perform kosaraju's algorithm and find the scc to which each planet belongs to,.. while performing the second dfs,.. we also mark the planets with the current position of the kingdom,.. which is denoted in the above code by the variable c declared in line 76

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &finish, ll &timer, vector<ll> &vis)
{
    vis[node] = 1;
    for (auto &i : adj[node])
    {
        if (vis[i] == 0)
        {
            dfs(i, adj, finish, timer, vis);
        }
    }
    finish[node] = timer++;
}
void dfs2(ll node, vector<ll> &vis, vector<vector<ll>> &adj, ll king, vector<ll> &kingdom)
{
    vis[node] = 1;
    kingdom[node] = king;
    for (auto &i : adj[node])
    {
        if (vis[i] == 0)
        {
            dfs2(i, vis, adj, king, kingdom);
        }
    }
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1);
    vector<vector<ll>> adjt(n + 1);
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adjt[y].push_back(x);
    }
    vector<ll> finish(n + 1, -1);
    vector<ll> vis(n + 1, 0);
    ll timer = 0;
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            dfs(i, adj, finish, timer, vis);
        }
    }
    vector<ll> ord(n);
    for (ll i = 0; i < n; i++)
    {
        ord[i] = i + 1;
    }
    sort(ord.begin(), ord.end(), [&](ll a, ll b)
         { return (finish[a] > finish[b]); });
    vis.clear();
    vis.resize(n + 1, 0);
    ll cnt = 0;
    vector<ll> nodes;
    vector<ll> kingdom(n + 1, -1);
    ll c = 0;
    for (ll i = 0; i < n; i++)
    {
        if (vis[ord[i]] == 0)
        {
            c++;
            dfs2(ord[i], vis, adjt, c, kingdom);
        }
    }
    cout << c << "\n";
    for (ll i = 1; i <= n; i++)
    {
        cout << kingdom[i] << " ";
    }
}

this is a classical problem of 2-SAT recommended reading material: https://cp-algorithms.com/graph/2SAT.html

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int tval[200005];
vector<int> adj[200005], adj2[200005];
vector<int> v;
bool vis[200005];
void dfs(int s)
{
    if (vis[s])
        return;
    vis[s] = 1;
    for (auto i : adj[s])
        dfs(i);
    v.push_back(s);
}
int k = 0;
int comp[200005];
void dfs2(int s)
{
    if (vis[s])
        return;
    vis[s] = 1;
    comp[s] = k;
    for (auto i : adj2[s])
        dfs2(i);
}
int main()
{
    // fastio;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        char x, y;
        int a, b;
        cin >> x >> a >> y >> b;
        if (x == '-')
            a = 2 * m - a + 1;
        if (y == '-')
            b = 2 * m - b + 1;
        adj[2 * m - a + 1].push_back(b);
        adj[2 * m - b + 1].push_back(a);
        adj2[a].push_back(2 * m - b + 1);
        adj2[b].push_back(2 * m - a + 1);
    }
    for (int i = 1; i <= 2 * m; i++)
    {
        if (!vis[i])
            dfs(i);
    }
    memset(vis, 0, sizeof vis);
    reverse(v.begin(), v.end());
    for (auto i : v)
    {
        int x = i;
        if (!vis[x])
        {
            k++;
            dfs2(x);
        }
    }
    for (ll i = 1; i <= m; i++)
    {
        if (comp[i] == comp[2 * m - i + 1])
        {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
        tval[i] = (comp[i] > comp[2 * m - i + 1]);
    }
    for (ll i = 1; i <= m; i++)
    {
        cout << ((tval[i]) ? '+' : '-') << " ";
    }
}

we convert the given graph to a DAG,.. so the collector can visit one node os the DAG and collect all the coins which were originally present in the nodes which were converted to this node in the DAG to make it easier to implement SCC,.. I have made a class SCCmaker,.. u can go through the above code and save it as a template to easily implement conversion of a graph to a DAG in future :)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}

class SCCmaker
{
    vector<vector<ll>> DAG;
    vector<ll> info;
    ll number_of_nodes;

    void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &vis, vector<ll> &order)
    {
        vis[node] = 1;
        for (auto &i : adj[node])
        {
            if (vis[i] != 1)
            {
                dfs(i, adj, vis, order);
            }
        }
        order.push_back(node);
    }
    void dfs2(ll node, vector<vector<ll>> &revadj, vector<ll> &temp, vector<ll> &vis)
    {
        vis[node] = 1;
        temp.push_back(node);
        for (auto &i : revadj[node])
        {
            if (vis[i] == 0)
            {
                dfs2(i, revadj, temp, vis);
            }
        }
    }

public:
    SCCmaker(vector<vector<ll>> &adj, vector<ll> &information, ll (*combine)(vector<ll> &temp, vector<ll> &information), vector<pair<ll, ll>> &edges, ll n)
    {
        vector<ll> order;
        vector<ll> vis(n + 1, 0);
        for (ll i = 1; i <= n; i++)
        {
            if (!vis[i])
                dfs(i, adj, vis, order);
        }
        reverse(order.begin(), order.end());
        vector<ll> vis2(n + 1, 0);
        vector<vector<ll>> revadj(n + 1);
        for (auto &i : edges)
        {
            revadj[i.second].push_back(i.first);
        }
        vector<ll> parentset(n + 1, 0);
        ll c = 0;
        for (auto &i : order)
        {
            if (!vis2[i])
            {
                vector<ll> temp;
                dfs2(i, revadj, temp, vis2);
                ll z = temp.size();
                for (ll j = 0; j < z; j++)
                {
                    parentset[temp[j]] = c;
                }
                ll sum = combine(temp, information);
                info.push_back(sum);
                c++;
            }
        }
        DAG.resize(c);
        number_of_nodes = c;
        for (auto &i : edges)
        {
            if (parentset[i.first] != parentset[i.second])
            {
                DAG[parentset[i.first]].push_back(parentset[i.second]);
            }
        }
    }
    vector<vector<ll>> getDAG()
    {
        return DAG;
    }
    vector<ll> getinfo()
    {
        return info;
    }
    ll get_numberofnodes()
    {
        return number_of_nodes;
    }
};
ll combine(vector<ll> &temp, vector<ll> &information)
{
    ll sum = 0;
    for (auto &i : temp)
    {
        sum += information[i - 1];
    }
    return sum;
}
ll solve(ll node, vector<vector<ll>> &DAG, vector<ll> &DAGinfo, vector<ll> &dp)
{
    ll res = 0;
    if (dp[node] != -1)
        return dp[node];
    for (auto &i : DAG[node])
    {
        res = max(res, solve(i, DAG, DAGinfo, dp));
    }
    return dp[node] = (res + DAGinfo[node]);
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<ll> val(n);
    for (auto &i : val)
    {
        cin >> i;
    }
    vector<vector<ll>> adj(n + 1);
    vector<pair<ll, ll>> edges;
    for (ll i = 1; i <= m; i++)
    {
        ll x, y;
        cin >> x >> y;
        edges.push_back({x, y});
        adj[x].push_back(y);
    }
    SCCmaker sccmaker(adj, val, combine, edges, n);
    ll DAGnodes = sccmaker.get_numberofnodes();
    vector<vector<ll>> DAG = sccmaker.getDAG();
    vector<ll> DAGinfo = sccmaker.getinfo();
    vector<ll> dp(DAGnodes + 1, -1);
    ll res = 0;
    for (ll i = 0; i < DAGnodes; i++)
    {
        res = max(res, solve(i, DAG, DAGinfo, dp));
    }
    cout << res << "\n";
}

recommended reading material: https://cp-algorithms.com/graph/euler_path.html I have implemented the algorithm as described in the article above

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<set<ll>> adj(n + 1);
    vector<ll> deg(n + 1, 0);
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].insert(y);
        adj[y].insert(x);
        deg[x]++;
        deg[y]++;
    }
    stack<ll> st;
    for (ll i = 1; i <= n; i++)
    {
        if (deg[i] % 2)
        {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    vector<ll> path;
    st.push(1);
    while (st.size() > 0)
    {
        ll x = st.top();
        if (deg[x] == 0)
        {
            st.pop();
            path.push_back(x);
        }
        else
        {

            ll z = *(adj[x].begin());
            adj[x].erase(z);
            adj[z].erase(x);
            deg[x]--;
            deg[z]--;
            st.push(z);
        }
    }
    if (path.size() != (m + 1))
    {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    for (auto &i : path)
    {
        cout << i << " ";
    }
}

recommended reading material: https://cses.fi/book/book.pdf#page=188

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll n;
    cin >> n;
    if (n == 1)
    {
        cout << "01\n";
        return 0;
    }
    ll N = (1 << (n - 1)) - 1;
    vector<vector<ll>> adj(N + 1);
    vector<ll> indeg(N + 1);
    vector<ll> outdeg(N + 1);
    for (ll i = 0; i <= N; i++)
    {
        ll num1 = (i * 2) % (1 << (max(0ll, (n - 1))));
        ll num2 = ((i * 2) + 1) % (1 << (max(0ll, (n - 1))));
        // cout << i << " " << num1 << " " << num2 << "\n";
        adj[i].push_back(num1);
        adj[i].push_back(num2);
        outdeg[i] += 2;
        indeg[num1]++;
        indeg[num2]++;
    }
    vector<ll> path;
    stack<ll> st;
    st.push(0);
    while (st.size() > 0)
    {
        ll x = st.top();
        if ((indeg[x] == 0) && (outdeg[x] == 0))
        {
            path.push_back(x);
            st.pop();
        }
        else
        {
            ll k = adj[x].back();
            adj[x].pop_back();
            indeg[k]--;
            outdeg[x]--;
            st.push(k);
        }
    }
    reverse(path.begin(), path.end());
    // for (auto &i : path)
    // {
    //     cout << i << " ";
    // }
    string res = "";
    for (ll i = 0; i < n - 1; i++)
    {
        res += '0';
    }
    ll m = path.size();

    for (ll i = 0; i < m - 1; i++)
    {
        if (path[i + 1] == ((path[i] * 2) % (1 << (max(0ll, (n - 1))))))
        {
            res += '0';
        }
        else
        {
            res += '1';
        }
    }
    // reverse(res.begin(), res.end());
    cout << res << "\n";
    // for (auto &i : path)
    // {
    //     cout << i << " ";
    // }
}

this is a classic problem of finding the euler path recommended reading material: https://cp-algorithms.com/graph/euler_path.html I have implemented the algorithm as described in the article above

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    fastio;
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<vector<ll>> adj(n + 1);
        vector<ll> indeg(n + 1, 0);
        vector<ll> outdeg(n + 1, 0);
        for (ll i = 0; i < m; i++)
        {
            ll x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            indeg[y]++;
            outdeg[x]++;
        }
        for (ll i = 2; i < n; i++)
        {
            if (indeg[i] != outdeg[i])
            {
                cout << "IMPOSSIBLE\n";
                return 0;
            }
        }
        if (((outdeg[1] - indeg[1]) != 1) || ((outdeg[n] - indeg[n]) != -1))
        {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
        stack<ll> st;
        st.push(1);
        vector<ll> path;
        while (st.size() > 0)
        {
            ll z = st.top();
            if ((indeg[z] == 0) && (outdeg[z] == 0))
            {
                path.push_back(z);
                st.pop();
            }
            else
            {
                ll m = adj[z].size();
                st.push(adj[z][m - 1]);
                adj[z].pop_back();
                outdeg[z]--;
                indeg[adj[z][m - 1]]--;
            }
        }
        if (path.size() != (m + 1))
        {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
        reverse(path.begin(), path.end());
        for (auto &i : path)
        {
            cout << i << " ";
        }
    }
}

it is the simple backtracking implementation of number of hamiltonian paths a mask variable is used in dfs to keep track of the nodes visited,.. if we reach the node n and the mask is 0(i.e. all the nodes are visited) then this counts as a valid path otherwise if the mask is not 0,..then it is not a valid path,.. and we return 0 we use a DP to memoize the results

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
#define MOD 1000000007
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
// ll mod = (ll)(1e9 + 7);
// vector<vector<int>> dp((1 << 21), vector<int>(21, -1));
ll dp[1 << 21][22];
vector<int> adj[22];
int n;
ll dfs(int mask, int node)
{
    mask = mask ^ (1 << (node));
    if ((mask == 0) && (node == (n - 1)))
    {
        return 1;
    }
    if (node == (n - 1))
    {
        return 0;
    }
    if (dp[mask][node] != -1)
    {
        return dp[mask][node];
    }
    // ll res = 0;
    // dp[mask][node] = 0;
    ll res = 0;
    for (auto &i : adj[node])
    {
        if ((1ll << (i)) & mask)
        {
            res += dfs(mask, i);
            res %= MOD;
        }
    }
    return (dp[mask][node] = res);
}
int main()
{
    fastio;
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        adj[x].push_back(y);
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs((1 << n) - 1, 0);
}

here also we use backtracking,.. but we need to find only one solution.. so instead of randomly choosing the next square for the knight to move,.. we sort the available squares according to the number of squares available to go from them in a non increasing order. This allows us to always visit the square from which we have the maximum chance of having a next place to move the knight to and hence optimizes the solution PS: without this optimization,. the code will give tle

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
ll board[8][8];
bool issafe(int x, int y)
{
    return (((0 <= x) && (x < 8)) && ((0 <= y) && (y < 8)));
}
int deg(ll x, ll y)
{
    int s = 0;
    for (ll i = 0; i < 8; i++)
    {
        ll nx = x + dx[i];
        ll ny = y + dy[i];
        if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] != -1))
            s++;
    }
    return s;
}
bool dfs(int x, int y, int move)
{
    board[x][y] = move;
    if (move == 64)
    {
        return true;
    }
    vector<vector<int>> vec;
    for (int i = 0; i < 8; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] == 0))
        {
            int d = deg(nx, ny);
            vec.push_back({d, nx, ny});
        }
    }
    sort(vec.begin(), vec.end());
    for (auto &i : vec)
    {
        if (dfs(i[1], i[2], move + 1))
            return true;
    }
    board[x][y] = 0;
    return false;
}
int main()
{
    fastio;
    ll x, y;
    cin >> y >> x;
    x--;
    y--;
    memset(board, 0, sizeof(board));
    bool res = dfs(x, y, 1);
    for (auto &i : board)
    {
        for (auto &j : i)
        {
            cout << j << " ";
        }
        cout << "\n";
    }
}

this is a problem of finding the maximum flow in a graph this is solved by implementing the ford fulkerson algorithm recommended reading material: https://cses.fi/book/book.pdf#page=191 I personally recommend to use the scaling algorithm to find paths for the ford fulkerson algorithm as it is easier to implement scaling algorithm: https://cses.fi/book/book.pdf#page=195

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis)
{
    vis[node] = 1;
    if (node == dest)
    {
        path.push_back(node);
        return true;
    }
    for (ll i = 1; i <= dest; i++)
    {
        if (adj[node][i] == -1)
            continue;
        if (vis[i])
            continue;
        if (adj[node][i] < threshhold)
        {
            continue;
        }
        if (dfs(i, dest, adj, path, threshhold, vis))
        {
            path.push_back(node);
            return true;
        }
    }
    return false;
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));
    ll sum = 0;
    for (ll i = 0; i < m; i++)
    {
        ll x, y, w;
        cin >> x >> y >> w;
        if (adj[x][y] == -1)
        {
            adj[x][y] = 0;
        }
        adj[x][y] += w;
        adj[y][x] = 0;
        sum += w;
    }
    ll ans = 0;
    while (sum > 0)
    {
        vector<ll> path;
        vector<ll> vis(n + 1, 0);
        bool f = dfs(1, n, adj, path, sum, vis);
        if (f == true)
        {
            reverse(path.begin(), path.end());
            ll k = path.size();
            ll minedgewt = LLONG_MAX;
            for (ll i = 0; i < k - 1; i++)
            {
                minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
            }
            ans += minedgewt;
            for (ll i = 0; i < k - 1; i++)
            {
                adj[path[i]][path[i + 1]] -= minedgewt;
                adj[path[i + 1]][path[i]] += minedgewt;
            }
        }
        else
            sum /= 2;
    }
    cout << ans << "\n";
}

this is a problem of the finding the minimum cut this is implemented using the ford fulkerson algorithm it is strongly recommended to either solve or read the editorial of download speed problem proceeding recommended reading material: https://cses.fi/book/book.pdf#page=195

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)
{
    vis[node] = 1;
    if (node == dest)
    {
        path.push_back(node);
        return true;
    }
    for (ll i = 1; i <= n; i++)
    {
        if (adj[node][i] == -1)
            continue;
        if (vis[i])
            continue;
        if (adj[node][i] < threshhold)
        {
            continue;
        }
        if (dfs(i, dest, adj, path, threshhold, vis, n))
        {
            path.push_back(node);
            return true;
        }
    }
    return false;
}
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)
{
    visited[node] = 1;
    left.push_back(node);
    for (ll i = 1; i <= n; i++)
    {
        if (visited[i])
            continue;
        if (og[node][i] <= 0)
            continue;
        dfs2(i, og, left, visited, n);
    }
}
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));
    vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));
    ll sum = 0;
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        ll w = 1;
        cin >> x >> y;
        og[x][y] = w;
        og[y][x] = w;
        if (adj[x][y] == -1)
        {
            adj[x][y] = 0;
            adj[y][x] = 0;
        }
        adj[x][y] += w;
        adj[y][x] += w;
        sum += w;
    }
    ll ans = 0;
    while (sum > 0)
    {
        vector<ll> path;
        vector<ll> vis(n + 1, 0);
        bool f = dfs(1, n, adj, path, sum, vis, n);
        if (f == true)
        {
            reverse(path.begin(), path.end());
            ll k = path.size();
            ll minedgewt = LLONG_MAX;
            for (ll i = 0; i < k - 1; i++)
            {
                minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
            }
            ans += minedgewt;
            for (ll i = 0; i < k - 1; i++)
            {
                adj[path[i]][path[i + 1]] -= minedgewt;
                adj[path[i + 1]][path[i]] += minedgewt;
            }
        }
        else
            sum /= 2;
    }
    cout << ans << "\n";
    vector<ll> left;
    vector<ll> visited(n + 1, 0);
    dfs2(1, adj, left, visited, n);
    unordered_set<ll> st;
    for (auto &i : left)
        st.insert(i);
    for (auto &i : left)
    {
        for (ll j = 1; j <= n; j++)
        {
            if (((og[i][j] == 1) && (adj[i][j] == 0)) && (st.find(j) == st.end()))
            {
                cout << i << " " << j << "\n";
            }
        }
    }
}

this is a problem of finding the maximum matching recommended reading material: https://cses.fi/book/book.pdf#page=197 I have implemented this article in the above code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)
{
    vis[node] = 1;
    if (node == dest)
    {
        path.push_back(node);
        return true;
    }
    for (ll i = 0; i <= n; i++)
    {
        if (adj[node][i] == -1)
            continue;
        if (vis[i])
            continue;
        if (adj[node][i] < threshhold)
        {
            continue;
        }
        if (dfs(i, dest, adj, path, threshhold, vis, n))
        {
            path.push_back(node);
            return true;
        }
    }
    return false;
}
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)
{
    visited[node] = 1;
    left.push_back(node);
    for (ll i = 0; i <= n; i++)
    {
        if (visited[i])
            continue;
        // if (og[node][i] == -1)
        //     continue;
        // if (og[node][i] == 0)
        //     continue;
        if (og[node][i] <= 0)
            continue;
        dfs2(i, og, left, visited, n);
    }
}
int main()
{
    fastio;
    ll n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> adj(n + m + 2, vector<ll>(n + m + 2, -1));
    vector<vector<ll>> og(n + m + 2, vector<ll>(n + m + 2, -1));
    ll sum = 0;
    for (ll i = 0; i < k; i++)
    {
        ll x, y;
        ll w = 1;
        cin >> x >> y;
        y += n;
        // y += 500;
        og[x][y] = w;
        // og[y][x] = w;
        // og[y][x] = w;
        if (adj[x][y] == -1)
        {
            adj[x][y] = 0;
            // adj[y][x] = 0;
        }
        adj[x][y] = w;
        adj[y][x] = 0;
        sum += w;
    }
    for (ll i = 1; i <= n; i++)
    {
        adj[0][i] = 1;
        og[0][i] = 1;
    }
    for (ll i = n + 1; i <= n + m; i++)
    {
        adj[i][n + m + 1] = 1;
        og[i][n + m + 1] = 1;
    }
    ll ans = 0;
    while (sum > 0)
    {
        vector<ll> path;
        vector<ll> vis(n + m + 2, 0);
        bool f = dfs(0, n + m + 1, adj, path, sum, vis, n + m + 1);
        if (f == true)
        {
            reverse(path.begin(), path.end());
            ll z = path.size();
            ll minedgewt = LLONG_MAX;
            for (ll i = 0; i < z - 1; i++)
            {
                minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
            }
            ans += minedgewt;
            for (ll i = 0; i < z - 1; i++)
            {
                adj[path[i]][path[i + 1]] -= minedgewt;
                adj[path[i + 1]][path[i]] += minedgewt;
            }
        }
        else
            sum /= 2;
    }
    // for (ll i = 0; i <= n + m + 1; i++)
    // {
    //     for (ll j = 0; j <= n + m + 1; j++)
    //     {
    //         cout << adj[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    cout << ans << "\n";
    vector<ll> left;
    // vector<ll> visited(n + m + 2, 0);
    // dfs2(0, adj, left, visited, n + m + 1);
    for (ll i = 1; i <= n; i++)
    {
        left.push_back(i);
    }
    unordered_set<ll> st;
    for (auto &i : left)
    {
        st.insert(i);
    }
    for (auto &i : left)
    {
        for (ll j = n + 1; j <= n + m; j++)
        {
            if (((og[i][j] == 1) && (adj[i][j] == 0)))
            {
                cout << i << " " << j - n << "\n";
            }
        }
    }
}

this is a problem of finding the maximum flow again read this: https://cses.fi/book/book.pdf#page=196 this article helps you to find the length of the path now to find the path.. we do this: start from vertex 1 go through all the edges,.. and check if there is an edge,.. whose reverse edge(that we artificially create in ford fulkerson algorithm) has a value,.. and this edge has value 0 this means that this edge is included in the max flow path we coninue this till we reach the end finally we print the answer. We maintain a set of pairs to make sure we don't consider an edge twice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)
{
    vis[node] = 1;
    if (node == dest)
    {
        path.push_back(node);
        return true;
    }
    for (ll i = 1; i <= n; i++)
    {
        if (adj[node][i] == -1)
            continue;
        if (vis[i])
            continue;
        if (adj[node][i] < threshhold)
        {
            continue;
        }
        if (dfs(i, dest, adj, path, threshhold, vis, n))
        {
            path.push_back(node);
            return true;
        }
    }
    return false;
}
// void dfs2(ll node, vector<vector<ll>> &adj, vector<vector<ll>> &og, ll n, set<pair<ll, ll>> &st)
// {
//     if (node != n)
//         cout << node << " ";
//     else if (node == n)
//         cout << node << "\n";
//     for (ll i = 1; i <= n; i++)
//     {
//         if (((adj[node][i] == 0) && (og[node][i] == 1)) && (st.find({node, i}) == st.end()))
//         {
//             st.insert({node, i});
//             dfs2(i, adj, og, n, st);
//         }
//     }
// }
// bool dfs2(ll node, ll n, vector<vector<ll>> &adj, vector<vector<ll>> &og, vector<vector<ll>> &paths)
// {
//     for (ll i = 1; i <= n; i++)
//     {
//         if ((adj[node][i] == 0) && (og[node][i] == 1))
//         {

//         }
//     }
// }
int main()
{
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));
    vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));
    ll sum = 0;
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        ll w = 1;
        cin >> x >> y;
        og[x][y] = w;
        if (adj[x][y] == -1)
        {
            adj[x][y] = 0;
        }
        adj[x][y] = w;
        if (adj[y][x] == -1)
            adj[y][x] = 0;
        sum += w;
    }
    ll ans = 0;
    while (sum > 0)
    {
        vector<ll> path;
        vector<ll> vis(n + 1, 0);
        bool f = dfs(1, n, adj, path, sum, vis, n);
        if (f == true)
        {
            reverse(path.begin(), path.end());
            ll z = path.size();
            ll minedgewt = LLONG_MAX;
            for (ll i = 0; i < z - 1; i++)
            {
                minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
            }
            ans += minedgewt;
            for (ll i = 0; i < z - 1; i++)
            {
                adj[path[i]][path[i + 1]] -= minedgewt;
                adj[path[i + 1]][path[i]] += minedgewt;
            }
        }
        else
            sum /= 2;
    }
    cout << ans << "\n";
    set<pair<ll, ll>> ed;
    // unordered_set<ll> ed;
    for (ll i = 0; i < ans; i++)
    {
        vector<ll> v = {1};
        int x = 1;
        while (x != n)
        {
            for (ll i = 1; i <= n; i++)
            {
                if (((adj[x][i] == 0) && (og[x][i] == 1)) && (ed.find({x, i}) == ed.end()))
                {
                    v.push_back(i);
                    ed.insert({x, i});
                    x = i;
                    break;
                }
            }
        }
        cout << v.size() << "\n";
        for (auto i : v)
            cout << (i) << " ";
        cout << "\n";
    }
}