LeetCode-Graph-Basic-/210. Course Schedule II.cpp at master · israkul9/LeetCode-Graph-Basic- · 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

class Solution {

	int graph[2000][2000];
	int visited[2000];
	int indegree[2000];
	queue <int> qq;
	vector <int> ans;


public:
	vector<int> findOrder(int numCourses, vector<vector<int>>& arr) {

		ans.clear();
		ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


		memset(visited, false , sizeof visited);

		for (auto it : arr) {
			vector <int> tmp = it;
			int a = tmp[0];
			int b = tmp[1];
			graph[b][a] = 1;
			indegree[a]++;
		}


		for (int i = 0; i < numCourses; i++) {
			if (indegree[i] == 0 and visited[i] == false) {
				visited[i] = true;
				qq.push(i);
			}
		}

		while (!qq.empty()) {
			int x = qq.front();
			qq.pop();
			//cout << x << " ";
			ans.push_back(x);

			for (int i = 0; i < numCourses; i++)
			{
				if (graph[x][i] == 1 and visited[i] == 0)
				{
					indegree[i]--;
					if (indegree[i] == 0)
					{
						qq.push(i);
						visited[i] = true;
					}
				}
			}


		}
        if(ans.size()==numCourses)
		return ans;
        else{
            ans.clear();
            return ans;
        }


	}
};