HDU.1285 确定比赛名次 (拓扑排序 TopSort)

HDU.1285 确定比赛名次 (拓扑排序 TopSort)

题意分析

裸的拓扑排序 详解请移步 算法学习 拓扑排序（TopSort） 只不过这道的额外要求是，输出字典序最小的那组解。那么解决方案就是每次扫描1-n节点的入度，并且只取出1个编号最小的节点，处理他然后继续取，直到所有节点取出，即可满足字典序最小。

代码总览

#include <iostream> #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <sstream> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #define nmax 505 #define MEM(x) memset(x,0,sizeof(x)) using namespace std; int indegree[nmax]; vector<int> v[nmax]; int n,m; queue<int> ans; bool suc = true;bool isfirst = true; void output() { while(!ans.empty()){ int t = ans.front(); ans.pop(); if(isfirst){printf("%d",t); isfirst =false;} else printf(" %d",t); } //printf("\n"); } void topsort() { queue<int> q; while(1){ for(int i = 1; i<=n;++i){ if(indegree[i] == 0){ q.push(i); ans.push(i); indegree[i] = -1; break; } } if(q.empty()) break; while(!q.empty()){ int t = q.front();q.pop(); for(int i = 0; i<v[t].size();++i){ int tt = v[t][i]; if(indegree[tt] == -1){ suc =false; break; }else indegree[tt] --; } v[t].clear(); if(!suc) break; } if(!suc) break; output(); } if(suc && ans.size() != n) suc = false; } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF){ MEM(indegree); suc = true;isfirst = true; for(int i = 0; i<m; ++i){ int a,b; scanf("%d%d",&a,&b); indegree[b]++; v[a].push_back(b); } topsort(); printf("\n"); } return 0; }