7-13 任务调度的合理性

拓扑排序：

是对有向无环图的顶点的一种排序

在AOV网中，先找到一个没有入度的顶点，然后输出

从网中删除这个顶点和所有以它为起点的有向边

重复以上步骤直至当前AOV网为空或网中不存在无前驱的顶点为止（这是有环图）

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

输入格式:

输入说明：输入第一行给出子任务数N（≤100），子任务按1~N编号。随后N行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数K，随后给出K个子任务编号，整数之间都用空格分隔。

输出格式:

如果方案可行，则输出1，否则输出0。

输入样例1:

12
0
0
2 1 2
0
1 4
1 5
2 3 6
1 3
2 7 8
1 7
1 10
1 7

输出样例1:

1

输入样例2:

5
1 4
2 1 4
2 2 5
1 3
0

输出样例2:

0

#include<bits/stdc++.h>
using namespace std;
int n,k,d[110]={0},x;
vector<int>g[110];//这就是一个邻接表，用于表示图的关系，每个元素都是向量类型的对象
bool topo(){
    int ans=0;
    queue<int>q;
    for(int i=1;i<=n;i++){
         if(d[i]==0)
        q.push(i),ans++;//入度为0，能入队，ans+1
        }
    while(!q.empty()){
        int u=q.front();
        q.pop();//及时弹出才能利用q.front()查找入度为0的点的出度
        for(unsigned int i=0;i<g[u].size();i++){//这个g[u].size()是获取u的邻接节点出度数量，入度不是邻接节点
            int v=g[u][i];//节点u的邻接表中的第i个节点
            d[v]--;
            if(d[v]==0) q.push(v),ans++;
        }
    }
    if(ans==n)return 1;//说明都能一个接一个的入队，最终都可以入度为0，没有限制，故成功
    return 0;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){  //这个循环的目的是建一个图，之后拓扑判断这个图
        cin>>k;
        while(k--){
            cin>>x;
            g[x].push_back(i);//将节点i加入x的邻接列表，从x指向i
            d[i]++;
        }
    }
    cout<<topo();
    return 0;
}