sicily 1004. Ordering Tasks

来源:互联网 发布:c语言 输入英文名 编辑:IT博客网 时间:2019/09/17 15:11

原理

优先元素可以进行排序

思路:

  1. 查找入度为0的点
  2. 放入优先队列中实现排序
  3. 利用优先元素实现类似BFS的收索并pop掉优先元素
#include<stdio.h>#include<queue>#include<vector>#include<memory.h>using namespace std;int indeg[100001];//记录入度 vector<int> nodes[1000001];//装领接的边的顶点 int main(){    int T;    int n,m;    scanf("%d",&T);    while(T--){        memset(indeg,0,sizeof(indeg));//初始化        scanf("%d%d",&n,&m);        while(m--){            int x,y;            scanf("%d%d",&x,&y);            nodes[x].push_back(y);            indeg[y]++;        }        priority_queue<int,vector<int>,greater<int> > q;         for(int i=1;i<=n;i++){//查找入度为0的点            if(indeg[i]==0){                q.push(i);            }           }        while(!q.empty()){            int temp=q.top();            q.pop();            printf("%d ",temp);            for(int i=0;i<nodes[temp].size();i++){                indeg[nodes[temp][i]]--;                if(indeg[nodes[temp][i]]==0){                    q.push(nodes[temp][i]);                }            }           }               for(int i=0;i<n;i++){            nodes[i].clear();        }        printf("\n");    }    return 0;}                                 
0 0