Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank DAG Queries Problem Solution

Yashwant Parihar, May 22, 2023May 28, 2024

In this post, we will solve HackerRank DAG Queries Problem Solution. You are given a Directed Acyclic Graph (DAG) with n vertices and m edges. Each vertex v has an integer, a,, associated with it and the initial value of a, is 0 for all vertices. You must perform q queries on the DAG, where each query is one of the following types: 1. 1 u x: Seta, to æ for all v such that there is a path in the DAG from u to v. 2.2 u x: Seta, to æ for all v such that there is a path from u to v and a, > x. 3.3 u: Print the value of a,, on a new line.
Input Format
The first line contains three space-separated integers describing the respective values of n (the number of vertices in the DAG), m (the number of edges in the DAG), and g (the number of queries to perform).
Each of the m subsequent lines contains two space-separated integers describing the respective values of u and u (where 1 <u, v < n. uv) denoting a directed edge from vertex u to vertex in the graph.
Each of the q subsequent lines contains a query in one of the three formats described above.

Output Format

For each query of type a (i.e., 3 u), print the value of au on a new line.

Sample Input 0

6 5 18
1 2
1 3
3 4
2 4
5 6
1 1 3
3 1
3 2
3 3
3 4
1 2 2
3 1
3 2
3 3
3 4
2 6 7
3 5
3 6
2 1 3
3 1
3 2
3 3
3 4

Sample Output 0

3
3
3
3
3
2
3
2
0
0
3
2
3
2
HackerRank DAG Queries Problem Solution
HackerRank DAG Queries Problem Solution

DAG Queries C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
typedef pair<int, int> pii;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

#define tm suka

const int maxc = 1e9;

//const int maxn = 1001;
const int maxn = 100100;
vector<int> g[maxn];

int tm[maxn];

int qt[maxn];
int qu[maxn];
int qx[maxn];
int qans[maxn];

//const int sn = 1;
const int sn = 600;
const int sn2 = 1000;
const int block = maxn / 3 + 2;
bitset<block> bs[maxn];
bool used[maxn];
int L, R;
int n;

vector<int> ord;

void pre(int u) {
    used[u] = true;
    for (int v: g[u])
        if (!used[v])
            pre(v);
    ord.push_back(u);
}

void uin(int &a, int b) {
    a = min(a, b);
}

void uax(int &a, int b) {
    a = max(a, b);
}

int a[maxn / sn + 2][maxn];

int upd[maxn];
vector<pii> o;
void put1(int u, int x) {
    o.emplace_back(u, x);
    if (sz(o) < sn2)
        return;
    forn (i, n)
        upd[i] = -1;
    for (auto p: o)
        uax(upd[p.first], p.second);
    o.clear();
    for (int ii = n - 1; ii >= 0; --ii) {
        int u = ord[ii];
        tm[u] = max(tm[u], upd[u]);
        for (int v: g[u])
            uax(upd[v], upd[u]);
    }
}

int get1(int u) {
    int res = tm[u];
    for (auto op: o)
        if (bs[op.first][u - L])
            uax(res, op.second);
    return res;
}

vector<int> q2;

void calc2(int l, int r) {
    int k = l / sn;
    forn (i, n)
        a[k][i] = maxc;
    for (int i = l; i < r; ++i) {
        int id = q2[i];
        uin(a[k][qu[id]], qx[id]);
    }
    for (int ii = n - 1; ii >= 0; --ii) {
        int u = ord[ii];
        for (int v: g[u])
            uin(a[k][v], a[k][u]);
    }
}

int get2(int u, int l, int r) {
    l = lower_bound(q2.begin(), q2.end(), l) - q2.begin();
    r = lower_bound(q2.begin(), q2.end(), r) - q2.begin();
    int res = maxc;
    int l2 = ((l + sn - 1) / sn) * sn;
    int r2 = (r / sn) * sn;
    if (l2 > r2) {
        for (int i = l; i < r; ++i) {
            int id = q2[i];
            int v = qu[id];
            if (bs[v][u - L])
                uin(res, qx[id]);
        }
    } else {
        for (int i = l; i < l2; ++i) {
            int id = q2[i];
            int v = qu[id];
            if (bs[v][u - L])
                uin(res, qx[id]);
        }
        for (int i = r2; i < r; ++i) {
            int id = q2[i];
            int v = qu[id];
            if (bs[v][u - L])
                uin(res, qx[id]);
        }
        l2 /= sn, r2 /= sn;
        for (int i = l2; i < r2; ++i)
            uin(res, a[i][u]);
    }
    return res;
}

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    int m, q;
    cin >> n >> m >> q;
    forn (i, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u, --v;
        g[u].push_back(v);
    }
    forn (i, n)
        if (!used[i])
            pre(i);
    forn (i, q) {
        int t, u, x = -1;
        scanf("%d%d", &t, &u);
        --u;
        if (t != 3)
            scanf("%d", &x);
        qt[i] = t, qu[i] = u, qx[i] = x;
    }

    forn (i, q) {
        if (qt[i] != 2)
            continue;
        q2.push_back(i);
    }
    for (int i = 0; i + sn <= sz(q2); i += sn)
        calc2(i, i + sn);

    for (L = 0; L < n; L += block) {
        R = min(n, L + block);
        forn (i, n) {
            bs[i].reset();
            tm[i] = -1;
        }
        o.clear();

        forn (i, n) {
            int u = ord[i];
            if (L <= u && u < R)
                bs[u][u - L] = true;
            for (int v: g[u])
                bs[u] |= bs[v];
        }

        forn (id, q) {
            if (qt[id] == 3) {
                int u = qu[id];
                if (u < L || u >= R)
                    continue;
                int lb = get1(u);
                int val = lb >= 0 ? qx[lb] : 0;
                uin(val, get2(u, lb, id));
                qans[id] = val;
            }
            if (qt[id] == 1)
                put1(qu[id], id);
        }
    }
    forn (i, q) {
        if (qt[i] == 3)
            cout << qans[i] << '\n';
    }
}

DAG Queries Scala Solution

object Assert {
    def check(e: Boolean) {
        if (!e) {
            throw new AssertionError();
        }
    }
}

class Scanner(is: java.io.InputStream) {

    val buffer: Array[Byte] = new Array[Byte](1 << 16);

    var len: Int = 0;

    var pos: Int = 0;

    def nextChar(): Int = {
        if (pos == len) {
            val read: Int = is.read(buffer);
            if (read == -1) {
                return -1;
            }
            len = read;
            pos = 0;
        }
        Assert.check(pos < len);
        val value: Int = buffer(pos) & 0xFF;
        pos += 1;
        return value;
    }

    def nextInt(): Int = {
        var c: Int = nextChar();
        while (c == ' ' || c == '\n' || c == '\r' || c == '\t') {
            c = nextChar();
        }
        Assert.check('0' <= c && c <= '9');
        var value: Int = c - '0';
        c = nextChar();
        while ('0' <= c && c <= '9') {
            val digit: Int = c - '0';
            Assert.check(value < Int.MaxValue / 10 || value == Int.MaxValue / 10 && digit <= Int.MaxValue % 10);
            value = value * 10 + digit;
            c = nextChar();
        }
        return value;
    }
}

class IntArrayList {

    var a: Array[Int] = new Array[Int](4);

    var size: Int = 0;
    
    def add(x: Int): Unit = {
        if (size == a.length) {
            a = java.util.Arrays.copyOf(a, a.length * 2);
        }
        a(size) = x;
        size += 1;
    }
    
    def get(i: Int): Int = {
        Assert.check(i < size);
        return a(i);
    }
}

class Query(val typ: Int, val node: Int, val value: Int) {}

object Solution {

    def reorder(parents: Array[IntArrayList], queries: Array[Query]): Unit = {
        val nV: Int = parents.size;
        val startOrder: Array[Int] = new Array[Int](nV);
        {
            var i: Int = 0;
            while (i < nV) {
                startOrder(i) = i;
                i += 1;
            }
        }
        var rnd: java.util.Random = new java.util.Random(20161106);
        {
            var i: Int = nV - 1;
            while (i > 0) {
                val j: Int = rnd.nextInt(i + 1);
                val t: Int = startOrder(i);
                startOrder(i) = startOrder(j);
                startOrder(j) = t;
                i -= 1;
            }
        }
        val orderedId: Array[Int] = new Array[Int](nV);
        java.util.Arrays.fill(orderedId, -1);
        val stack: IntArrayList = new IntArrayList();
        val ip: IntArrayList = new IntArrayList();
        var nextId: Int = 0;
        {
            var i: Int = 0;
            while (i < nV) {
                if (orderedId(startOrder(i)) == -1) {
                    stack.add(startOrder(i));
                    ip.add(0);
                    while (stack.size > 0) {
                        val cur: Int = stack.a(stack.size - 1);
                        if (ip.get(ip.size - 1) == parents(cur).size) {
                            orderedId(cur) = nextId;
                            nextId += 1;
                            stack.size -= 1;
                            ip.size -= 1;
                        } else {
                            val p: Int = parents(cur).get(ip.get(ip.size - 1));
                            ip.a(ip.size - 1) += 1;
                            if (orderedId(p) == -1) {
                                stack.add(p);
                                ip.add(0);
                            }
                        }
                    }
                }
                i += 1;
            }
        }
        if (false) {
            print("new ids: ");
            var first: Boolean = true;
            {
                var i: Int = 0;
                while (i < nV) {
                    if (first) {
                        first = false;
                    } else {
                        print(", ");
                    }
                    print((i + 1) + " -> " + (orderedId(i) + 1));
                    i += 1;
                }
            }
            println();
        }
        Assert.check(nextId == nV);
        {
            var i: Int = 0;
            while (i < orderedId.length) {
                Assert.check(orderedId(i) >= 0);
                i += 1;
            }
        }
        val orderedParents: Array[IntArrayList] = new Array[IntArrayList](nV);
        {
            var i: Int = 0;
            while (i < nV) {
                orderedParents(i) = new IntArrayList();
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nV) {
                {
                    var ip: Int = 0;
                    while (ip < parents(i).size) {
                        val p: Int = parents(i).get(ip);
                        orderedParents(orderedId(i)).add(orderedId(p));
                        ip += 1;
                    }
                }
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nV) {
                java.util.Arrays.sort(orderedParents(i).a, 0, orderedParents(i).size);
                parents(i) = orderedParents(i);
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < queries.length) {
                val typ: Int = queries(i).typ;
                val node: Int = queries(i).node;
                val value: Int = queries(i).value;
                Assert.check(0 <= node && node < nV);
                queries(i) = new Query(typ, orderedId(node), value);
                i += 1;
            }
        }
    }

    def process(
        parents: Array[IntArrayList],
        queries: Array[Query],
        qFirst: Int,
        qAfter: Int,
        a: Array[Int],
        codes: Array[Long],
        add: Array[Int],
        min: Array[Int],
        result: IntArrayList
    ): Unit = {
        val nV: Int = parents.length;
        val q12: IntArrayList = new IntArrayList();
        {
            var q = qFirst;
            while (q < qAfter) {
                if (queries(q).typ < 3) {
                    q12.add(q);
                }
                q += 1;
            }
        }
        if (q12.size == 0) {
            var q: Int = qFirst;
            while (q < qAfter) {
                Assert.check(queries(q).typ == 3);
                val node: Int = queries(q).node;
                Assert.check(0 <= node && node < nV);
                result.add(a(node));
                q += 1;
            }
            return;
        }
        val n: Int = q12.size;
        Assert.check(n <= 8 * 14);
        Assert.check(nV <= 100000);
        java.util.Arrays.fill(codes, 0, nV * 2, 0);
        {
            var i: Int = 0;
            while (i < n) {
                val node: Int = queries(q12.get(i)).node;
                val word: Int = i / 56;
                val shift: Int = i % 56 / 14 * 16 + i % 14; // 14 used bits, 2 free
                codes(node * 2 + word) |= 1L << shift;
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nV) {
                {
                    val pari: IntArrayList = parents(i);
                    var ip: Int = 0;
                    while (ip < pari.size) {
                        val p: Int = pari.get(ip);
                        codes((i << 1) + 0) |= codes((p << 1) + 0);
                        codes((i << 1) + 1) |= codes((p << 1) + 1);
                        ip += 1;
                    }
                }
                i += 1;
            }
        }
        var q: Int = qFirst;
        var part: Int = 0;
        while (part * 14 < n) {
            val begin: Int = part * 14;
            val end: Int = Math.min(n, begin + 14);
            val codesAdd: Int = part / 4;
            val codesShift: Int = part % 4 * 16;
            // a = Math.min(a + add, min)
            add(0) = 0;
            min(0) = 1000 * 1000 * 1000;
            var bit: Int = 0;
            while (bit < end - begin) {
                val qType: Int = queries(q12.get(begin + bit)).typ;
                val value: Int = queries(q12.get(begin + bit)).value;
                val extra: Int = 1 << bit;
                if (qType == 1) { // assign
                    var code: Int = 0;
                    while (code < extra) {
                        add(code + extra) = 1000 * 1000 * 1000;
                        min(code + extra) = value;
                        code += 1;
                    }
                } else {
                    Assert.check(qType == 2); // min
                    var code: Int = 0;
                    while (code < extra) {
                        add(code + extra) = add(code);
                        min(code + extra) = Math.min(value, min(code));
                        code += 1;
                    }
                }
                bit += 1;
            }
            var mask = 0;
            while (end == n && q != qAfter || end != n && q != q12.get(end)) {
                if (queries(q).typ < 3) {
                    mask <<= 1;
                    mask |= 1;
                } else {
                    Assert.check(queries(q).typ == 3);
                    val node: Int = queries(q).node;
                    val code: Int = ((codes((node << 1) + codesAdd) >> codesShift) & mask).toInt;
                    val answer: Int = Math.min(a(node) + add(code), min(code));
                    result.add(answer);
                }
                q += 1;
            }
            var i = 0;
            while (i < nV) {
                val code: Int = ((codes((i << 1) + codesAdd) >> codesShift) & 0xFFFF).toInt;
                a(i) = Math.min(a(i) + add(code), min(code));
                i += 1;
            }
            part += 1;
        }
    }

    def solveFast(parents: Array[IntArrayList], queries: Array[Query]): IntArrayList = {
        val nV: Int = parents.length;
        {
            var i: Int = 0;
            while (i < nV) {
                {
                    var ip: Int = 0;
                    while (ip < parents(i).size) {
                        val p: Int = parents(i).get(ip);
                        Assert.check(p < i); // parents before children
                        ip += 1;
                    }
                }
                i += 1;
            }
        }
        val a: Array[Int] = new Array[Int](nV);
        val codes: Array[Long] = new Array[Long](100000 * 2);
        val add: Array[Int] = new Array[Int](1 << 14);
        val min: Array[Int] = new Array[Int](1 << 14);
        val result: IntArrayList = new IntArrayList();
        val MAX12Q = 8 * 14;
        var first: Int = 0;
        var n12q: Int = 0;
        val nQ: Int = queries.length;
        {
            var i: Int = 0;
            while (i < nQ) {
                if (queries(i).typ < 3) {
                    n12q += 1;
                }
                if (n12q == MAX12Q || i == nQ - 1) {
                    process(parents, queries, first, i + 1, a, codes, add, min, result);
                    first = i + 1;
                    n12q = 0;
                }
                i += 1;
            }
        }
        return result;
    }

    def main(args: Array[String]): Unit = {
        val in: Scanner = new Scanner(System.in);
        val nV: Int = in.nextInt();
        val nE: Int = in.nextInt();
        val nQ: Int = in.nextInt();
        val parents: Array[IntArrayList] = new Array[IntArrayList](nV);
        {
            var i: Int = 0;
            while (i < nV) {
                parents(i) = new IntArrayList();
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nE) {
                val parent: Int = in.nextInt() - 1;
                val child: Int = in.nextInt() - 1;
                parents(child).add(parent);
                i += 1;
            }
        }
        val queries: Array[Query] = new Array[Query](nQ);
        {
            var i: Int = 0;
            while (i < nQ) {
                val qType: Int = in.nextInt();
                if (qType == 1 || qType == 2) {
                    val parent: Int = in.nextInt() - 1;
                    val value: Int = in.nextInt();
                    queries(i) = new Query(qType, parent, value);
                } else {
                    Assert.check(qType == 3);
                    val node: Int = in.nextInt() - 1;
                    queries(i) = new Query(qType, node, -1);
                }
                i += 1;
            }
        }
        reorder(parents, queries);
        val result: IntArrayList = solveFast(parents, queries);
        {
            var i: Int = 0;
            while (i < result.size) {
                println(result.get(i));
                i += 1;
            }
        }
    }
}

DAG Queries Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  static class MyBitSet {
    private final static int ADDRESS_BITS_PER_WORD = 6;
    private long[] words;
    private transient int wordsInUse = 0;

    private static int wordIndex(int bitIndex) {
      return bitIndex >> ADDRESS_BITS_PER_WORD;
    }

    public MyBitSet(int nbits) {
      words = new long[wordIndex(nbits - 1) + 1];
    }

    public void clear() {
      while (wordsInUse > 0)
        words[--wordsInUse] = 0;
    }

    public void set(int bitIndex) {
      int wordIndex = wordIndex(bitIndex);
      expandTo(wordIndex);
      words[wordIndex] |= (1L << bitIndex);
    }

    private void expandTo(int wordIndex) {
      int wordsRequired = wordIndex + 1;
      if (wordsInUse < wordsRequired) {
        wordsInUse = wordsRequired;
      }
    }


    public void or(MyBitSet set) {
      int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

      if (wordsInUse < set.wordsInUse) {
        wordsInUse = set.wordsInUse;
      }

      for (int i = 0; i < wordsInCommon; i++) {
        words[i] |= set.words[i];
      }

      if (wordsInCommon < set.wordsInUse) {
        System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
            wordsInUse - wordsInCommon);
      }
    }

    public boolean get(int bitIndex) {
      int wordIndex = wordIndex(bitIndex);
      return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }
  }

  static class PS {
    int opt;
    int u;
    int x;
    int i;
  }

  static class QS {
    int u;
    int i;

    public QS(int u, int i) {
      this.u = u;
      this.i = i;
    }
  }

  static Set<Integer>[] graph;
  static int[] indeg;
  static int[] topo;
  static int ttot = 1;

  static void topo_dfs(int node) {
    topo[ttot++] = node;
    for (int i = ptr[node]; i > 0; i = nxt[i]) {
      if (--indeg[succ[i]] == 0) {
        topo_dfs(succ[i]);
      }
    }
  }

  static int[] nxt;
  static int[] succ;
  static int[] ptr;
  static int index = 1;

  static void addedge(int u, int v) {
    nxt[index] = ptr[u];
    ptr[u] = index;
    succ[index++] = v;
  }


  static final int B = 316;

  static int[] solve2(int[][] queries, int n, int nQue) {
    int q = queries[0].length - 1;
    int[] ans = new int[q + 1];

    QS[] que = new QS[nQue + 1];
    PS[] perform = new PS[q + 1];
    int ptot = 0;
    int qtot = 0;

    for (int i = 1; i <= q; i++) {
      perform[ptot] = new PS();
      perform[ptot].opt = queries[0][i];
      if (perform[ptot].opt <= 2) {
        perform[ptot].u = queries[1][i];
        perform[ptot].x = queries[2][i];
        perform[ptot++].i = i;
      } else {
        que[qtot++] = new QS(queries[1][i], i);
      }
      ans[i] = Integer.MAX_VALUE;
    }

    MyBitSet[] b = new MyBitSet[n + 1];
    for (int i = n; i > 0; i--) {
      b[i] = new MyBitSet(320);
    }

    boolean[] cover = new boolean[n + 1];
    int[] minVal = new int[n + 1];

    for (int l = (ptot - 1) - (ptot - 1) % B, r = ptot - 1; l >= 0; r = l - 1, l -= B) {
      for (int i = n; i > 0; i--) {
        b[i].clear();
      }

      for (int i = l; i <= r; ++i) {
        b[perform[i].u].set(i - l);
      }

      for (int i = 1; i <= n; i++) {
        for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) {
          b[succ[j]].or(b[topo[i]]);
        }
      }

      Arrays.fill(cover, false);

      for (int i = l; i <= r; i++) {
        if (perform[i].opt == 1) {
          cover[perform[i].u] = true;
        }
      }

      for (int i = 1; i <= n; i++) {
        if (cover[topo[i]]) {
          for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) {
            cover[succ[j]] = true;
          }
        }
      }

      Arrays.fill(minVal, Integer.MAX_VALUE);

      for (int i = l; i <= r; i++) {
        if (perform[i].opt == 2) {
          minVal[perform[i].u] = Math.min(minVal[perform[i].u], perform[i].x);
        }
      }

      for (int i = 1; i <= n; ++i) {
        for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) {
          minVal[succ[j]] = Math.min(minVal[succ[j]], minVal[topo[i]]);
        }
      }


      int i = qtot;
      while (i > 0 && que[i - 1].i > perform[l].i) {
        i--;
      }
      while (i < qtot) {
        if (que[i].i < perform[r].i) {
          int j = r;
          while (perform[j].i > que[i].i) {
            --j;
          }
          for (; j >= l; j--)
            if (b[que[i].u].get(j - l)) {
              ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x);
              if (perform[j].opt == 1) {
                --qtot;
                QS temp = que[i];
                que[i] = que[qtot];
                que[qtot] = temp;
                break;
              }
            }
          i += j < l ? 1 : 0;
        } else if (cover[que[i].u]) {
          int j = r;
          for (; perform[j].opt == 2 || !b[que[i].u].get(j - l); j--) {
            if (perform[j].opt == 2 && b[que[i].u].get(j - l)) {
              ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x);
            }
          }
          ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x);

          --qtot;
          QS temp = que[i];
          que[i] = que[qtot];
          que[qtot] = temp;

        } else {
          ans[que[i].i] = Math.min(ans[que[i].i], minVal[que[i].u]);
          i++;
        }

      }
    }
    while (qtot-- > 0) {
      ans[que[qtot].i] = 0;
    }
    return ans;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    graph = new Set[n + 1];
    Set<Integer>[] parent = new Set[n + 1];

    for (int i = 1; i <= n; i++) {
      graph[i] = new HashSet<>();
      parent[i] = new HashSet<>();
    }

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());
      graph[u].add(v);
      parent[v].add(u);
    }

    int[][] queries = new int[3][q + 1];
    int[] convert = new int[n + 1];
    int nodes = 0;
    int op3 = 0;

    for (int i = 1; i <= q; i++) {
      st = new StringTokenizer(br.readLine());
      queries[0][i] = Integer.parseInt(st.nextToken());
      int u = Integer.parseInt(st.nextToken());

      if (convert[u] == 0) {
        nodes++;
        convert[u] = nodes;
      }

      queries[1][i] = convert[u];
      if (queries[0][i] <= 2) {
        int x = Integer.parseInt(st.nextToken());
        queries[2][i] = x;
      } else {
        op3++;
      }
    }

    for (int u = 1; u <= n; u++) {
      if (convert[u] == 0) {
        for (int v : parent[u]) {
          graph[v].remove(u);
          graph[v].addAll(graph[u]);
        }
        for (int v : graph[u]) {
          parent[v].remove(u);
          parent[v].addAll(parent[u]);
        }
        
        parent[u] = null;
        graph[u] = null;
      }
    }

    indeg = new int[nodes + 1];
    boolean[] existDeg = new boolean[nodes + 1];

    nxt = new int[m + 1];
    ptr = new int[nodes + 1];
    succ = new int[m + 1];

    for (int u1 = 1; u1 <= n; u1++) {
      int u = convert[u1];
      if (u > 0) {
        for (int v1 : graph[u1]) {
          int v = convert[v1];
          indeg[v]++;
          existDeg[v] = true;
          addedge(u, v);
        }
      }
    }

    topo = new int[nodes + 1];
    for (int i = nodes; i > 0; i--) {
      if (!existDeg[i]) {
        topo_dfs(i);
      }
    }

    int[] ans = solve2(queries, nodes, op3);

    for (int i = 1; i <= q; i++) {
      if (ans[i] < Integer.MAX_VALUE) {
        bw.write(ans[i] + "\n");
      }
    }

    bw.close();
    br.close();
  }
}
C++ HackerRank Solutions java Scala cppHackerrank SolutionsjavaScala

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes