# Question 1
# in Q1, the students_order will always have enough information to sort student by student's height

students = set(["a", "b", "c"])
students_order = [["a", "b"],["c", "b"],["a", "c"]]

a < b
c < b

a < c

["a", "c", "b"]

students = array(set(["a", "b", "c"]))

students_order = [["a", "b"],["b", "c"]]
["a", "b", "c"]

students = set(["a", "b", "c"])

students_order = [["a", "b"]]

result = []

"""
constraints

the given input matches the real status (no cycle)
"""
# Q5

courses = set([a,b,c,d])
course_order = [[a,b], [b,c], [d,c]]

[a,d,b,c]
[a,b,d,c] <-
[d,a,b,c]

depend: {a: [b], b: [c]}
indegree: {b: 0, c: 1}

q: []
ans: [a, d, b, c]

vector<string> sortStudents(vector<string>& courses, vector<vector<string>> courseOrder) {    
    unordered_map<string, vector<string>> depend;
    unordered_map<string, int> indegree;
    for (int i = 0; i < courseOrder.size(); i++) {
        depend[courseOrder[i][0]].push_back(courseOrder[i][1]);
        indegree[courseOrder[i][1]]++;
    }
    
    ordered_set<string> q;
    for (string& student: courses) {
        if (indegree.find(student) == indegree.end()) {
            q.push(student);
        }
    }
    
    vector<string> ans;
    while (!q.empty()) {
        string node = q[0];
        q.pop(0);
        ans.push_back(node);
        
        for (string& nextNode: depend[node]) {
            indegree[nextNode]--;
            if (indegree[nextNode] == 0) {
                q.push(nextNode);
            }
        }
    }
    
    if (ans.size() != courses.size()) {
        return {};
    }
    return ans;
}

# Q4

courses = set([a,b,c,d])
course_order = [[a,b], [b,c], [d,c]]

[a,d,b,c]
[a,b,d,c]

depend: {a: [b], b: [c]}
indegree: {b: 0, c: 1}

q: []
ans: [a, d, b, c]

vector<string> sortStudents(vector<string>& courses, vector<vector<string>> courseOrder) {    
    unordered_map<string, vector<string>> depend;
    unordered_map<string, int> indegree;
    for (int i = 0; i < courseOrder.size(); i++) {
        depend[courseOrder[i][0]].push_back(courseOrder[i][1]);
        indegree[courseOrder[i][1]]++;
    }
    
    queue<string> q;
    for (string& student: courses) {
        if (indegree.find(student) == indegree.end()) {
            q.push(student);
        }
    }
    
    vector<string> ans;
    while (!q.empty()) {
        if (q.size() >= 2) {
            return {};
        }
        string node = q.front();
        q.pop();
        ans.push_back(node);
        
        for (string& nextNode: depend[node]) {
            indegree[nextNode]--;
            if (indegree[nextNode] == 0) {
                q.push(nextNode);
            }
        }
    }
    
    if (ans.size() != courses.size()) {
        return {};
    }
    return ans;
}

# Q3
a -> d
b -> d
c -> d
a -> b => a < b
b -> c => b < c

a -> ... -> d
a: a's indegree == 0
d: d's outdegree == 0

students = ["a", "b", "c", "d"]
// students_order = [["a", "b"], ["a", "c"], ["c", "b"], ["c", "d"], ["b", "d"]]
students_order = [["a", "b"], ["a", "c"], ["c", "d"], ["b", "d"]]

depend = {a: [b, c], b: [d], c: [d]}
indegree = {b: 0, c: 0, d: 2}
q = [b, c]
ans = [a]

vector<string> sortStudents(vector<string>& students, vector<vector<string>> students_order) {    
    unordered_map<string, vector<string>> depend;
    unordered_map<string, int> indegree;
    for (int i = 0; i < students_order.size(); i++) {
        depend[students_order[i][0]].push_back(students_order[i][1]);
        indegree[students_order[i][1]]++;
    }
    
    queue<string> q;
    for (string& student: students) {
        if (indegree.find(student) == indegree.end()) {
            q.push(student);
            break;
        }
    }
    
    vector<string> ans;
    while (!q.empty()) {
        string node = q.front();
        q.pop();
        ans.push_back(node);
        
        for (string& nextNode: depend[node]) {
            indegree[nextNode]--;
            if (indegree[nextNode] == 0) {
                q.push(nextNode);
            }
        }
        if (q.size() >= 2) {
            return {};
        }
    }
    
    if (ans.size() != students.size()) {
        return {};
    }
    return ans;
}

# Q2
a -> d
b -> d
c -> d
a -> b => a < b
b -> c => b < c

a -> ... -> d
a: a's indegree == 0
d: d's outdegree == 0

students = ["a", "b", "c"]
students_order = [["a", "b"],["b", "c"], ["a", "b"]]

depend = {a: [b, b], b: [c]}
indegree = {b: 0, c: 1}
q = []
seen = {b}
ans = [a]

vector<string> sortStudents(vector<string>& students, vector<vector<string>> students_order) {    
    unordered_map<string, vector<string>> depend;
    unordered_map<string, int> indegree;
    for (int i = 0; i < students_order.size(); i++) {
        depend[students_order[i][0]].push_back(students_order[i][1]);
        indegree[students_order[i][1]]++;
    }
    
    queue<string> q;
    for (string& student: students) {
        if (indegree.find(student) == indegree.end()) {
            q.push(student);
            break;
        }
    }
    
    vector<string> ans;
    while (!q.empty()) {
        string node = q.front();
        q.pop();
        ans.push_back(node);
        
        for (string& nextNode: depend[node]) {
            indegree[nextNode]--;
            if (indegree[nextNode] == 0) {
                q.push(nextNode);
            }
        }
    }
    
    for (auto& ind: indegree) {
        if (ind.second > 0) {
            return {};
        }
    }
    return ans;
}

a -> d
b -> d
c -> d
a -> b => a < b
b -> c => b < c

a -> ... -> d
a: a's indegree == 0
d: d's outdegree == 0

students = ["a", "b", "c"]
students_order = [["a", "b"],["b", "c"]]

depend = {a: [b], b: [c]}
indegree = {b: 1, c: 1}
q = []
ans = [a, b, c]

# Q1

vector<string> sortStudents(vector<string>& students, vector<vector<string>> students_order) {    
    unordered_map<string, vector<string>> depend;
    unordered_map<string, int> indegree;
    for (int i = 0; i < students_order.size(); i++) {
        depend[students_order[i][0]].push_back(students_order[i][1]);
        indegree[students_order[i][1]]++;
    }
    
    queue<string> q;
    for (string& student: students) {
        if (indegree.find(student) == indegree.end()) {
            q.push(student);
            break;
        }
    }
    
    vector<string> ans;
    while (!q.empty()) {
        string node = q.front();
        q.pop();
        ans.push_back(node);
        
        for (string& nextNode: depend[node]) {
            indegree[nextNode]--;
            if (indegree[nextNode] == 0) {
                q.push(nextNode);
            }
        }
    }
    return ans;
}