题目描述

给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

输入格式

第一行包含两个整数n和m

接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。

输出格式

共一行，如果存在拓扑序列，则输出拓扑序列。

否则输出-1。

数据范围

1≤n,m≤105

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

主要考点

拓扑排序

C ++ 代码 ---- 手写队列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int h[N], e[N], ne[N], idx;//邻接表
int q[N], hh, tt = -1;//模拟队列
int d[N];//存放各点入度
int n, m;

//在a和b之间添加一条边
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

//判断是否是拓扑序列
bool topsort(){
    for(int i = 1; i <= n; i ++){//将入度为0的点加入队列
        if(d[i] == 0) q[++ tt] = i;
    }

    while(hh <= tt){
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(-- d[j] == 0) q[++ tt] = j;
        }
    }
    if(tt == n - 1) return true;//是拓扑序列
    else return false;
}

int main(){
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;//入度 +1
    }
    if(topsort()){
        for(int i = 0; i <= tt; i ++){
            cout << q[i] << ' ';
        }
    }
    else cout << "-1" << endl;

    return 0;
}

C ++ 代码2 ---- STL

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
const int N = 100010;

int h[N], e[N], ne[N], idx;
queue<int> q;
int n, m;
int d[N];
int ways[N], cnt;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort(){
    for(int i = 1; i <= n; i ++){
        if(d[i] == 0) q.push(i), ways[++ cnt] = i;
    }
    while(q.size()){
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(-- d[j] == 0) q.push(j), ways[++ cnt] = j;
        }
    }
    if(cnt == n) return true;
    else return false;
}

int main(){
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }

    if(topsort()){
        for(int i = 1; i <= n; i ++){
            cout << ways[i] << ' ';
        }
    }
    else{
        cout << "-1" << endl;
    }

    return 0;
}