# Graph
###### tags: `Study_aboard`
## Find the celebrity ==Facebook==

Sol1: We can represent the question as a graph
Examples:

celeb is 1

No celeb

Brute force: To check if the node has no output edge and n input edge

bool knows(int a, int b);
class Solution {
public:
    int findCelebrity(int n) {
        vector<bool> candidate(n, true);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (candidate[i] && i != j) {
                    if (knows(i, j) || !knows(j, i)) {
                        candidate[i] = false;
                        break;
                    } else {
                        candidate[j] = false;
                    }
                }
            }
            if (candidate[i]) return i;
        }
        return -1;
    }
};

Sol2 ==better==

We can eliminate one member when we use know function
if know(a,b) return ```true```: we know that a cannot be the celebrity
if know(a,b) return ```false```: we know that b cannot be the celebrity

Therefore, we know that we can eliminate n-1 candidates by calling know function n-1 times, and we only need to check whether the last candidate is a celebrity

// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (knows(res, i)) res = i; 
            // if true, res cannot be celeb
            // if false, i cannot be celeb
        }
        for (int i = 0; i < n; ++i) {
            if (res != i && (knows(res, i) || !knows(i, res))) return -1;
        }
        return res;
    }
};

## Alien Dictionary ==Hard==

Use topological sort

class Solution {
public:
    string alienOrder(vector<string>& words) {
        vector<vector<bool>> g(26, vector<bool>(26)); // DAG
        vector<bool> visited(26); // vector to record visited nodes, true = current path, false = already visited or have not visited yet
        string res;

        for (string word : words) {
            for (char c : word) {
                g[c - 'a'][c - 'a'] = true; // g[i][i] = true means that the char is used in the word
            }
        }

        for (int i = 0; i < (int)words.size() - 1; ++i) {
            int mn = min(words[i].size(), words[i + 1].size()), j = 0;
            for (; j < mn; ++j) {
                if (words[i][j] != words[i + 1][j]) {
                    g[words[i][j] - 'a'][words[i + 1][j] - 'a'] = true; // g[i][j]=true means that there is an edge from i to j
                    break;
                }
            }
            if (j == mn && words[i].size() > words[i + 1].size()) return ""; // invalid order
        }

        for (int i = 0; i < 26; ++i) { // dfs for every nodes (char) that are used
            if (!dfs(g, i, visited, res)) return "";
        }
        return res;
    }
    bool dfs(vector<vector<bool>>& g, int idx, vector<bool>& visited, string& res) { // return false when invalid
        if (!g[idx][idx]) return true; // idx is not used in all words
        visited[idx] = true;
        for (int i = 0; i < 26; ++i) {
            if (i == idx || !g[i][idx]) continue; // skip i=idx and skip when no edge from i to idx
            if (visited[i]) return false; // i is already visited -> invalid
            if (!dfs(g, i, visited, res)) return false; 
        }
        visited[idx] = false;
        g[idx][idx] = false;
        res += 'a' + idx;
        return true;
    }
};