Minimum time taken by each job to be completed given by a Directed Acyclic Graph

minTimeDAG.cpp

/*
Author: Saurav Kumar Gupta
Problem: Minimum time taken by each job to be completed given by a Directed Acyclic Graph
Data Structures: Queue, Array
*/

#include "./../my_lib.h"
vector<int> adj[100005];

void findMinTime(int V) {
  vector<int> indegree(V + 1, 0);

  for (int i = 1; i <= V; i++) {
    for (int it : adj[i]) {
      indegree[it]++;
    }
  }

  vector<int> dist(V + 1, INT_MAX);
  queue<int> Q;

  for (int i = 1; i <= V; i++) {
    if (indegree[i] == 0) {
      Q.push(i);
      dist[i] = 1;
    }
  }

  while (!Q.empty()) {
    int node = Q.front(); Q.pop();

    for (int it : adj[node]) {
      indegree[it]--;

      if (indegree[it] == 0) {
        dist[it] = dist[node] + 1;
        Q.push(it);
      }
    }
  }

  for (int d : dist) cout << d << " ";
}

int main() {
  int V, m;
  cin >> V >> m;
  int a, b;

  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    // adj[b].push_back(a);
  }

  findMinTime(V);
}

/*
Input:
10
13
1 3
1 4
1 5
2 3
2 8
2 9
3 6
4 6
4 8
6 7
7 8
5 8
8 10

Output:
1 1 2 2 2 3 4 5 2 6 

*/