Preference List, C++ (gcc)

Preference List

/* 28 Preference List
# leetcode #269 Alien Dictionary
Given a list of everyone's preferred city list, output the city list 
following the order of everyone's preference order.
For example, input is [[3, 5, 7, 9], [2, 3, 8], [5, 8]]. 
One of possible output is [2, 3, 5, 8, 7, 9]. 
*/
//
// Solution: print out cities with in-degree = 0; 
//

#include <iostream>
#include <vector>
#include <set> 
#include <map>
#include <queue> 
using namespace std;

class CityList{
    map<int, set<int>> m; // x->y printing orderr
    map<int, set<int>> indegree; 
public:
    vector<int> getList(vector<vector<int>>& lists) {
        // find all nodes 
        set<int> all; 
        for(auto l: lists) all.insert(l.begin(), l.end());
        
        // init graph 
        for(auto l: lists) {
            for(int i=0; i<(int)l.size()-1; i++){
                int x = l[i], y =l[i+1];
                m[x].insert(y);
                indegree[y].insert(x); // easy to make mistake
            }
        }
        
        // find degree=0 nodes
        queue<int> frees; 
        for(auto x: all){
            if(indegree.count(x)==0) 
                frees.push(x);
        }
        
        // print in order 
        vector<int> res; 
        while(frees.size()){
            int x = frees.front(); frees.pop();
            //cout << "x="<< x << endl;
            res.push_back(x);
            if(m.count(x)==0) continue; // make codes clean 
            
            for(int y: m[x]){
                if(indegree.count(y)){
                    indegree[y].erase(x);
                    if(indegree[y].size()==0){ // free node apprear {
                        frees.push(y);
                        indegree.erase(y);
                    }
                }
            }
            
        }
        return res; 
    }
    void print(vector<int> v) {
        for(int i=0; i<(int) v.size(); i++){
            cout << v[i] ;
            if(i<(int)v.size()-1) cout << ", "; 
        }
        cout << endl;
    }
                       
};
int main(){
    vector<vector<int>> lists = {{3,5,7,9}, {2,3,8}, {8,5},{10}};
    CityList cl; 
    vector<int> res = cl.getList(lists);
    cl.print(res);
    return 0; 
}


run \| edit \| history \| help	0