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;

}