# HDU4857逃生(拓扑排序)

Description

Input

Output

Sample Input
1
5 10
3 5
1 4
2 5
1 2
3 4
1 4
2 3
1 5
3 5
1 2
Sample Output

1 2 3 4 5

#include<stdio.h>
#include<queue>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 100005
priority_queue<int,vector<int>,less<int > >q;//此处应该为从大到小
vector<int> map[MAX];
int indegree[MAX];
int que[MAX];//存储
void topsort(int n)
{
int i;
for(i=1;i<=n;i++)
if(indegree[i]==0)
q.push(i);
int j=0;
memset(que,0,sizeof(que));
while(!q.empty())
{
int v=q.top();
q.pop();
que[j++]=v;
for(int k=0;k<map[v].size();k++)
{
indegree[map[v][k]]--;
if(indegree[map[v][k]]==0)
q.push(map[v][k]);
}
}
for(i=j-1;i>0;i--)
printf("%d ",que[i]);
printf("%d\n",que);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(indegree,0,sizeof(indegree));
for(int i=1;i<=n;i++)
map[i].clear();
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
map[b].push_back(a);//将a放在b的后边，建立反向边的关系
indegree[a]++;
}
topsort(n);
}
return 0;
}
{"ft_lang_label":"__label__zh","ft_lang_prob":0.5446542,"math_prob":0.9949461,"size":1459,"snap":"2019-26-2019-30","text_gpt3_token_len":853,"char_repetition_ratio":0.11065292,"word_repetition_ratio":0.0,"special_character_ratio":0.37080193,"punctuation_ratio":0.19254659,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99681675,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-19T19:14:55Z\",\"WARC-Record-ID\":\"<urn:uuid:b892a741-3ef7-4465-83f7-c2178d92b47e>\",\"Content-Length\":\"127546\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:66f2c31e-e2e1-448e-bc8e-949cc2dcace0>\",\"WARC-Concurrent-To\":\"<urn:uuid:4ff40748-41d7-4c79-95ea-6c265d125ebf>\",\"WARC-IP-Address\":\"39.96.126.153\",\"WARC-Target-URI\":\"https://blog.csdn.net/zhaihao1996/article/details/52134225\",\"WARC-Payload-Digest\":\"sha1:XL4KBLPXFU3B34CWSRPW6A5GDSMSC7WU\",\"WARC-Block-Digest\":\"sha1:LVMOIWXVZOH23R6DRJ335WCZAO2ZZBVU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195526337.45_warc_CC-MAIN-20190719182214-20190719204214-00426.warc.gz\"}"}