// 1111111.cpp: 定义控制台应用程序的入口点。

 //

 #include "stdafx.h"

 #include <vector>

 #include <queue>

 using namespace std;

 bool canFinish1(int numCourses, vector<vector<int>>& prerequisites) {

     vector<vector<int> > graph(numCourses, vector<int>());

     vector<int> in(numCourses, );

     for (auto a : prerequisites) {

         graph[a[]].push_back(a[]);

         ++in[a[]];

     }

     queue<int> q;

     for (int i = ; i < numCourses; ++i) {

         if (in[i] == ) q.push(i);

     }

     while (!q.empty()) {

         int t = q.front();

         q.pop();

         for (auto a : graph[t]) {

             --in[a];

             if (in[a] == ) q.push(a);

         }

     }

     for (int i = ; i < numCourses; ++i) {

         if (in[i] != ) return false;

     }

     return true;

 }

 //==========================================================================

 bool canFinishDFS(vector<vector<int> > &graph, vector<int> &visit, int i) {

     if (visit[i] == -) return false;

     if (visit[i] == ) return true;

     visit[i] = -;

     for (auto a : graph[i]) {

         if (!canFinishDFS(graph, visit, a)) return false;

     }

     visit[i] = ;

     return true;

 }

 bool canFinish2(int numCourses, vector<vector<int> >& prerequisites) {

     vector<vector<int> > graph(numCourses, vector<int>());

     vector<int> visit(numCourses, );

     for (auto a : prerequisites) {

         graph[a[]].push_back(a[]);

     }

     for (int i = ; i < numCourses; ++i) {

         if (!canFinishDFS(graph, visit, i)) return false;

     }

     return true;

 }

 int main()

 {

     //测试数据

     {

         int i = ;

         vector<vector<int> > v;

         v.push_back(std::vector<int>{, });

         v.push_back(std::vector<int>{ ,});

         canFinish1(i , v);

     }

     //{

     //    int i = 2;

     //    vector<vector<int> > v;

     //    v.push_back(std::vector<int>{1, 0});

     //    v.push_back(std::vector<int>{0, 1});

     //}

     //{

     //    int i = 2;

     //    vector<vector<int> > v;

     //    v.push_back(std::vector<int>{1, 0});

     //}

     //{

     //    int i = 3;

     //    vector<vector<int> > v;

     //    v.push_back(std::vector<int>{1, 0});

     //    v.push_back(std::vector<int>{2, 0});

     //}

 //    {

 //        int i = 3;

 //        vector<vector<int> > v;

 //        v.push_back(std::vector<int>{1, 0});

 //        v.push_back(std::vector<int>{2, 0});

 //    }

 //

 //    {

 //        int i = 3;

 //        vector<vector<int> > v;

 //        v.push_back(std::vector<int>{0, 1});

 //        v.push_back(std::vector<int>{1, 2});

 //    }

 //

 //    {

 //        int i = 4;

 //        vector<vector<int> > v;

 //        v.push_back(std::vector<int>{0, 1});

 //        v.push_back(std::vector<int>{1, 2});

 //        v.push_back(std::vector<int>{2, 0});

 //        v.push_back(std::vector<int>{1, 3});

 //    }

 //

 //    {

 //        int i = 4;

 //        vector<vector<int> > v;

 //        v.push_back(std::vector<int>{0, 1});

 //        v.push_back(std::vector<int>{1, 2});

 //        v.push_back(std::vector<int>{1, 3});

 //    }

     return ;

 }