DAG topological sort 응용문제

void IDFS(vector<vector<int>> & graph, vector<bool> & visited, stack<int> & res, int target) {
    visited[target] = true;
    for (int i = 0; i < graph[target].size(); i++) {
        if (visited[graph[target][i]] == false) {
            IDFS(graph, visited, res, graph[target][i]);
        }
    }
    res.push(target);
}
 
vector<char> language(vector<string> & data) {
    // make char vector
    vector<vector<int>> graph(26, vector<int>());
    // parse data to fill char graph
    for (int i = 0; i < data.size() - 1; i++) {
        // compare strings to find char priority
        int curr = 0;
        while (curr < data[i].size() && curr < data[i + 1].size()) {
            if (data[i][curr] == data[i + 1][curr]) curr++;
            else {
                graph[data[i][curr] - 'a'].push_back(data[i + 1][curr] - 'a');
                break;
            }
        }
    }
    // do topological sort
    stack<int> res;
    vector<bool> visited(26, false);
    for (int i = 0; i < 26; i++) {
        if (visited[i] == false) {
            IDFS(graph, visited, res, i);
        }
    }
    vector<char> ret;
    while (res.size() != 0) {
        ret.push_back(res.top() + 'a');
        res.pop();
    }
    // validate cycle
    for (int i = 0; i < 26; i++) {
        for (int j = i + 1; j < 26; j++) {
            for (int k = 0; k < graph[ret[j] - 'a'].size(); k++) {
                if (graph[ret[j] - 'a'][k] == ret[i] - 'a') return vector<char>(1, 0);
            }
        }
    }
    return ret;
}