course-schedule

有点类似拓扑排序。简单。

注：Java数组中，每一个元素都要new。Set也是要new的。

https://leetcode.com/problems/course-schedule/
https://leetcode.com/mockinterview/session/result/xsuqirj/

// 用Java又做了一遍
package com.company;


import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

class Solution {
    class Node {
        Set<Integer> pre;
        Set<Integer> post;
        Node() {
            pre = new HashSet<>();
            post = new HashSet<>();
        }
     }

    public boolean canFinish(int n, int[][] p) {
        Node[] nd = new Node[n];
        Set<Integer> st = new HashSet<>();
        for (int i=0; i<n; i++) {
            st.add(i);
            nd[i] = new Node();
        }

        for (int i=0; i<p.length; i++) {
            int first = p[i][0];
            int second = p[i][1];
            nd[first].pre.add(second);
            nd[second].post.add(first);
            st.remove(first);
        }

        int finish = 0;
        while (!st.isEmpty()) {
            Set<Integer> newSt = new HashSet<>();
            Iterator<Integer> iter = st.iterator();
            while (iter.hasNext()) {
                int pos = iter.next();
                finish++;
                Iterator<Integer> posIter = nd[pos].post.iterator();
                while (posIter.hasNext()) {
                    int post = posIter.next();
                    nd[post].pre.remove(pos);
                    if (nd[post].pre.isEmpty()) {
                        newSt.add(post);
                    }
                }
            }
            st = newSt;
        }
        return (finish == n);
    }
}

public class Main {

    public static void main(String[] args) {
        // write your code here
        System.out.println("Hello");
        Solution solution = new Solution();

        int[][] p = {{1,0},{0,1}};
        boolean ret = solution.canFinish(2, p);
        System.out.printf("Get ret: %b
", ret);

    }
}


// C++版本

class Solution {
    set<int> st;
    map<int, set<int>> inde;
    map<int, set<int>> outde;
public:
    bool canFinish(int n, vector<pair<int, int>>& p) {
        int vlen = p.size();
        int ff;
        int ss;
        
        for (int i = 0; i < p.size(); ++i) {
            ff = p[i].first;
            ss = p[i].second;
            if (inde.find(ff) == inde.end()) {
                set<int> tmp;
                tmp.insert(ss);
                inde[ff] = tmp;
            }
            else {
                inde[ff].insert(ss);
            }
            if (outde.find(ss) == outde.end()) {
                set<int> tmp;
                tmp.insert(ff);
                outde[ss] = tmp;
            }
            else {
                outde[ss].insert(ff);
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (inde.find(i) == inde.end()) {
                st.insert(i);
            }
        }
        
        int learn;
        set<int> tmp;
        set<int>::iterator itr;
        while (!st.empty()) {
            learn = *(st.begin());
            st.erase(learn);
            
            if (outde.find(learn) != outde.end()) {
                tmp = outde[learn];
                for (itr = tmp.begin(); itr != tmp.end(); ++itr) {
                    inde[*itr].erase(learn);
                    if (inde[*itr].empty()) {
                        st.insert(*itr);
                        inde.erase(*itr);
                    }
                }
            }
        }
        
        if (!inde.empty()) {
            return false;
        }
        else {
            return true;
        }
        
    }
};