Input
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
Output
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3 1 2 2 3 4 3
Sample Output
1 2 4 3
给定一个包含 n 个节点的有向图 G,我们给出它的节点编号的一种排列,如果满足:
对于图 G 中的任意一条有向边 (u, v),u 在排列中都出现在 v 的前面。
那么称该排列是图 G 的「拓扑排序」。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int mx = 100010; //check the limits, dummy
typedef long long ll;
typedef pair<int, int> pa;
const double PI = acos(-1);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
#define swa(a,b) a^=b^=a^=b
#define re(i,a,b) for(ll i=(a),_=(b);i<_;i++)
#define rb(i,a,b) for(ll i=(b),_=(a);i>=_;i--)
#define clr(a) memset(a, 0, sizeof(a))
#define lowbit(x) ((x)&(x-1))
#define mkp make_pair
void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); }
using namespace std; int n,m; int in[N];//节点入度 int path[N];//存储路径 vector<int> G[N];//G[i]表示i节点所指向的所有其他点 void Topsort()//拓扑排序 { priority_queue< int,vector<int>,greater<int> > Q;//最小值先出列 int cnt=0;//记录可拆解的点数目 for(int i=1;i<=n;i++)//枚举编号从1到n的点 if(in[i]==0)//入度为0,入列 Q.push(i); while(!Q.empty()) { int x=Q.top();//队列首元素 Q.pop(); path[++cnt]=x;//存储可拆点 for(int i=0;i<G[x].size();i++){ int y=G[x][i]; in[y]--;//入度减一 if(in[y]==0)//入度为0,出列 Q.push(y); } } } int main() { while(scanf("%d%d",&n,&m)!=EOF&&n) { clr(in); re(i,1,n+1) G[i].clear(); re(i,1,m+1){ int x,y; scanf("%d%d",&x,&y); G[x].push_back(y); in[y]++; } Topsort(); re(i,1,n) printf("%d ",path[i]); cout<<path[n]; printf("\n"); } return 0; }