文章

27

粉丝

0

获赞

130

访问

8.3k

头像
P1566 确定比赛名次 答疑提问:
jsd VIP
P1566 中山大学机试题
发布于2025年2月23日 15:35
阅读数 316

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

const int maxn = 1000;
int gmap[maxn][maxn]; //邻接矩阵存储
int indegree[maxn];//入度
 
 
 
void topo(int n){
 	priority_queue<int,vector<int>,greater<int> > q;
 	int cnt;	
 	for(int i = 1;i<=n;i++){
 		if(indegree[i]==0){
 			q.push(i);
 			cnt++;
		 }
	 } 
	 
	 while(!q.empty()){
	 	int k = q.top();
	 	q.pop();//出队
	 	printf("%d ",k);
		 for(int i = 1;i<=n;i++){
		 	if(gmap[k][i] == 1){
		 		indegree[i]--;
		 		if(indegree[i] == 0){
		 			q.push(i);
		 			cnt++;
				 }
			 }
		 } 
		 
//		 if(cnt==n){
//		 	printf("OK");
//		 }else{
//		 	printf("有环");
//		 }
	 }
}
int main(){
	int n,m;
	while(cin>>n>>m){
		memset(gmap,0,sizeof(gmap));
		memset(indegree,0,sizeof(indegree));
		int a,b;
		for(int i = 0;i<m;i++){
			cin>>a>>b;//a赢了b 
			gmap[a][b] = 1;
			indegree[b]++;
		}
		
		topo(n);
		printf("\n");
	}
	
	return 0;
} 

求 为什么只能...

登录查看完整内容


登录后发布评论

2 条评论
admin SVIP
2025年2月23日 16:01

图的问题都要考虑一下重边的可能,除非题目明确说了没有重边

赞(1)

jsd : 回复 admin: 谢谢

2025年2月23日 20:00