FilesExpand file tree

 main

/

toposort.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

41 lines (35 loc) · 809 Bytes

 main

/

toposort.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

41 lines (35 loc) · 809 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

//Reverse DFS

void topo(int src,vector<int>* &v,int* vis,vector<int> &ans)

{

vis[src]=1;

for(int i=0;i<v[src].size();i++)

{

int cp=v[src][i];

if(vis[cp]==0)

{

topo(cp,v,vis,ans);

}

}

ans.push_back(src);

}

class Solution

{

public:

//Function to return list containing vertices in Topological order.

vector<int> topoSort(int n, vector<int> v[])

{

//To exist if a topo cycle exits

//Atfirst find if its a directed acyclic graph.

//Then,move here

int vis[n]={0}; vector<int>ans;

for(int i=0;i<n;i++)

{

if(vis[i]==0)

{

topo(i,v,vis,ans);

}

}

reverse(ans.begin(),ans.end());

return ans;

}

};