# HackerRank DAG Queries problem solution

In this HackerRank DAG Queries problem solution we have given a directed acyclic graph with n vertices and m edges and each vertex has an integer associated with and the initial value is zero for all vertices. we need to perform q queries on this acyclic graph.

## Problem solution in Java.

```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) {
}

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 {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

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++) {
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
}

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++) {
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);
}
for (int v : graph[u]) {
parent[v].remove(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;
}
}
}

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();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define tm suka

const int maxc = 1e9;

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 = 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<pair<int, int>> o;
void put1(int u, int x) {
o.emplace_back(u, x);
if ((int)o.size() < sn2)
return;
for (int i = 0; i < n; ++i)
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;
for (int i = 0; i < n; ++i)
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() {
int m, q;
cin >> n >> m >> q;

for (int i = 0; i < m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
--u, --v;
g[u].push_back(v);
}
for (int i = 0; i < n; ++i)
if (!used[i])
pre(i);

for (int i = 0; i < q; ++i) {
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;
}

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

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

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

for (int id = 0; id < q; ++id) {
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);
}
}
for (int i = 0; i < q; ++i) {
if (qt[i] == 3)
cout << qans[i] << '\n';
}
}
```

{"mode":"full","isActive":false}