order dependency

cpp.sh

// Example program
#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

vector<int> orderdependency(vector<pair<int, int> >& pre, int num)
{
    vector<int> ret;

    map<int, int> ind;

    for(unsigned int i = 0; i<num; i++)
    {
        ind[i] = 0;   
    }

    for(unsigned int i = 0; i<pre.size(); i++)
    {
        pair<int, int> cur = pre[i];
        ind[cur.first]++;   
    }

    while(ret.size() != num)
    {
        map<int, int>::iterator it = ind.begin();
        bool hasZero = false;
        for(; it != ind.end(); it++)
        {
            if(it->second != 0)
            {
                continue;
            }
            hasZero = true;
            ret.push_back(it->first);

            for(unsigned int i = 0; i<pre.size(); i++)
            {
                if(pre[i].second == it->first)
                {
                    ind[pre[i].first]--;   
                }
            }

            ind.erase(it->first);
        }
        if(hasZero == false)
        {
            vector<int> e;
            return e;
        }
    }


    return ret;
}


int main()
{
    vector<pair<int, int> > vec;


    vec.push_back(make_pair(1, 2));
    vec.push_back(make_pair(0, 2));
    vec.push_back(make_pair(3, 1));
    vec.push_back(make_pair(3, 2));

    vector<int> ret = orderdependency(vec, 4);
    for(unsigned int i = 0; i<ret.size(); i++)
    {
        cout<<ret[i]<<" ";   
    }

    return 1;
}

code

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

        vector<int> ret;

        if(prerequisites.size() == 0)
        {
            for(int i = 0; i<numCourses; i++)
            {
                ret.push_back(i);
            }
            return ret;
        }

        map<int, int> indegree;
        for(int i = 0; i<numCourses; i++)
        {
            indegree[i] = 0;
        }

        for(int i = 0; i<prerequisites.size(); i++)
        {
            pair<int, int> p = prerequisites[i];
            indegree[p.first]++;
        }

        while(ret.size() != numCourses)
        {

            map<int, int>::iterator it = indegree.begin();
            bool hasZero = false;
            for(; it != indegree.end(); it++)
            {

                if(it->second == -1)
                {
                    continue;
                }

                if(it->second != 0)
                {
                    continue;
                }

                hasZero = true;
                ret.push_back(it->first);

                for(int i = 0; i<prerequisites.size(); i++)
                {
                    pair<int, int> p = prerequisites[i];
                    if(p.second == it->first)
                    {
                        indegree[p.first]--;
                    }
                }

                it->second = -1;
            }

            if(hasZero == false)
            {
                vector<int> empty;
                return empty;
            }
        }

        return ret;


    }
};