图论--拓扑排序--模板

//字典序号最小
#include <cstdio>
#include <cstring>
#define MAXN 517
int G[MAXN][MAXN];   //路径
int in_degree[MAXN]; //入度
int ans[MAXN];
int n, m, x, y;
int i, j;

bool toposort()
{
    for (i = 1; i <= n; i++) //从最小的开始寻找，
    {                        //这样保证了有多个答案时序号小的先输出
        int k = 1;
        while (in_degree[k] != 0&&k<=n) //寻找入度为零的点
     	k++;
     	if(k==n+1)  return 0;
        ans[i] = k;
        in_degree[k] = -1;
        //更新为-1，后边检测不受影响，相当于删除节点
        for (int j = 1; j <= n; j++)
        {
            if (G[k][j])
                in_degree[j]--; //相关联的入度减1
        }
    }
    return 1;
}

void init()
{
    memset(in_degree, 0, sizeof(in_degree));
    memset(ans, 0, sizeof(ans));
    memset(G, 0, sizeof(G));
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        init();
        for (i = 0; i < m; i++)
        {
            scanf("%d%d", &x, &y);
            if(G[x][y]==0) in_degree[y]++;
            G[x][y] = 1;
            
        }
        toposort();
        for (i = 1; i < n; i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
    return 0;
}

//字典序最小2
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500+10;
int n,m;
vector<int> G[maxn];
int in[maxn];
void topo()
{
    priority_queue<int,vector<int>,greater<int> > Q; //保证小值int先出队列
    int ans[maxn],cnt=0;
    for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);
    while(!Q.empty())
    {
        int u=Q.top(); Q.pop();
        ans[cnt++]=u;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in[v]==0)
                Q.push(v);
        }
    }
    printf("%d",ans[0]);
    for(int i=1;i<n;i++)
        printf(" %d",ans[i]);
    puts("");
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            in[v]++;
        }
        topo();
    }
    return 0;
}

//一般的拓扑排序
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500+10;
int n,m;
vector<int> G[maxn];
int in[maxn];
void topo()
{
    priority_queue<int,vector<int>,greater<int> > Q; //保证小值int先出队列
    int ans[maxn],cnt=0;
    for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);
    while(!Q.empty())
    {
        int u=Q.top(); Q.pop();
        ans[cnt++]=u;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in[v]==0)
                Q.push(v);
        }
    }
    printf("%d",ans[0]);
    for(int i=1;i<n;i++)
        printf(" %d",ans[i]);
    puts("");
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            in[v]++;
        }
        topo();
    }
    return 0;
}