文章
27
粉丝
0
获赞
130
访问
8.3k
#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;
}
求 为什么只能...
登录后发布评论
图的问题都要考虑一下重边的可能,除非题目明确说了没有重边