Data-Structure_Algorithms_Coding/direc.cpp at main · Sdccoding/Data-Structure_Algorithms_Coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*Minimum time taken by each job to be completed given by a Directed Acyclic Graph*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
ll times[101];
ll vis[101];
void dfs(ll src,vector<ll>* adj,ll cp)
{
	vis[src]=1;
	times[src]=min(times[src],cp);
	for(auto x:adj[src])
	{
		if(vis[x]==0)
		{
			dfs(x,adj,cp+1);
		}
	}


}
int main()
{

    ll t;
    cin>>t;
    while(t--)
    {
    	ll n,e;
    	cin>>n>>e;
    	vector<ll>adj[n+1];
        memset(vis,0,sizeof(vis));
    	for(ll i=0;i<e;i++)
    	{
    		ll u,v;
    		cin>>u>>v;
    		adj[u].pb(v);
    		vis[v]++;
    	}
    	for(ll i=1;i<=n;i++) times[i]=INT_MAX;
    	queue<int>q;
    	for(ll i=1;i<=n;i++)
    	{
    		if(!vis[i])
    			q.push(i);
    	}
    	memset(vis,0,sizeof(vis));

    	while(q.size())
    	{
    		ll t=q.front();
    		q.pop();
    		if(vis[t]==0)
    		{

    			dfs(t,adj,1);
    		}
    	}

    	for(ll i=1;i<=n;i++)
    	{
    		cout<<times[i]<<" ";
    	}
    	cout<<endl;


    }
}