该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

输入顶点和边数，以及顶点关系，对其进行拓扑排序。（按照栈的特性进行拓扑排序，初始时按照按照1~n的顺序将入度为0的点加入栈中，注意：本题存在重边）

输入格式

第一行输入顶点数v和边数e 接下去输入e行的边关系

输出格式

如果图中存在环，则输出 has circle，否则，输出它的拓扑顺序。

样例

输入样例

样例输入1

4 4
1 2
1 3
4 3
2 4

样例输出1

1 2 4 3

输入样例

样例输入2

3 3
1 2
2 3
3 1

样例输出2

has circle

数据范围与提示

1<=e,v<=100000

注释代码

#include<bits/stdc++.h>
using namespace std;

stack<int> s;   //存入度为0的点
int n, m;   //n个点，m条边
vector<int> v[100005];   //v[i]存储节点i的所有终点
int d[100005];   //d[i]表示i的入度大小
queue<int> q;
int main(){
	cin >> n >> m;
	for(int i=1; i<=m; i++){  //有m条边
		int x, y;   //x -> y   //表示x走到y
		cin >> x >> y;    
		d[y]++;   //y的入度+1
		v[x].push_back(y);    //x点的后面有一个终点y
	}
	//循环把区间[1, n]的点中入度为0的点加入栈s
	for(int i=1; i<=n; i++){
		if(!d[i]) s.push(i);  //i入度为0，加入栈 
	}
	
	//只要栈不为空，说明还有入度为0的点，说明还没有走完
	//所以从这个点出发继续尝试走
	while(s.size()){   
		int x = s.top();   //取出栈顶
		s.pop();   //把栈顶删除
		q.push(x); 
		//从x这个点出发，把所有的能走到的点y入度-1
		//如果y的入度-1之后变成了0，那么把y加入栈
		for(int y : v[x]){   //遍历x能走到的所有点y
			d[y]--;
			if(d[y] == 0) s.push(y);
		}
	}
	if(q.size() != n) cout << "has circle";  //如果队列里面的点数量不等于n，说明有环
	else{
		while(q.size()){
			cout << q.front() << ' ';
			q.pop();
		}
	}
	return 0;
}