题意是给你一些关系,来进行排序,前面的那个人一定在后一个人前面,也在那些没有交钱的人的前面。。
我们用逆拓扑排序,先把入度为零的数从大到小存入数组。然后就是一般的拓扑排序。。最后逆序输出
<span style="font-size:24px;">#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<vector> using namespace std; int m,n; vector<int> s[30010]; int q[30010]; int e[30010]; int sum; void show() { priority_queue<int> Q; for (int i = 1; i <= n; i++) if (!q[i]) Q.push(i); while (!Q.empty()) { int now = Q.top(); Q.pop(); for (int i = 0; i < s[now].size(); i++) { q[s[now][i]]--; if (q[s[now][i]] == 0) Q.push(s[now][i]); } e[sum++] = now; } } int main() { int a,b,c,j,i; scanf("%d",&a); while(a--) { sum=0; memset(q,0,sizeof(q)); //memset(e,0,sizeof(e)); scanf("%d %d",&n,&m); for(i=1;i<=n;i++) s[i].clear(); for(i=0;i<m;i++) { scanf("%d %d",&b,&c); s[c].push_back(b); q[b]++; } show(); // for(i=1;i<=n;i++) // printf("%d ",q[i]); for(int i = sum - 1; i > 0; i--) printf("%d ", e[i]); printf("%d\n", e[0]); } return 0; }</span>