拓扑排序

• 求解过程：

  1）计算所有点的入度值

  2）寻找入度为0的点

  3）寻找这个点影响的其他连通点并把它们的入度值减去1

  4）循环进行2+3步，直到所有点都找到

• 可以判断图是否有环：若寻找不到入度为0的点则存在环

#include <iostream>
#include <queue> 
#include <cstring>
using namespace std;

struct edge { //链式前向星 - 实现遍历某点的所有边信息
    int e; //边的终点
    int next; //相同起点上一条边的编号
};
edge edg[1001]; 

int n; //点的数量
int m; //边的数量
int ans; //所有边权之和
int num[1001]; //拓扑排序的序列
int cnt; //当前选出了几个点
int inDegree[1001]; //保存入度数量
int head[1001]; //保留以每个点出发的所有边当中最后一条边所在edg下标

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        ++inDegree[b];
        edg[i].e = b;
        edg[i].next = head[a];
        head[a] = i;
    }
    queue<int> que;
    for (int i = 1; i <= n; ++i)
        if (0 == inDegree[i]) que.push(i);
    while (!que.empty()) {
        int tmp = que.front();
        que.pop();
        num[cnt++] = tmp;

        //寻找这个点影响的其他连通点并把它们的入度值减去1
        for (int i = head[tmp]; i != -1; i = edg[i].next) {
            int e = edg[i].e;
            if (0 == (--inDegree[e])) que.push(e);
        }
    }
    if (cnt != n) { //存在环
        cout << "Range!" << endl;
        return 0;
    }
    for (int i = 0; i < cnt; ++i) cout << num[i] << " ";
    cout << endl;
    return 0;
}

搜索与回溯 实现输出全部拓扑排序

#include <iostream>
#include <vector> //使用邻接表
using namespace std;

int n; //点的数量
int m; //边的数量
int r; //处理是否有环 
int num[1001]; //拓扑排序的序列
int mark[1005]; //标记数组进行去重 负责判断没有选择的点 值0-没有选择过 值1-已选择
int inDegree[1001]; //保存入度数量

//@params now-当前选择的数字
void func(int now, vector<vector<int> > &edg)
{
    if (now == n + 1) {
        for (int i = 1; i <= n; ++i)
            cout << num[i] << " ";
        cout << endl;
        r = 1;
        return ;
    }
    for (int i = 1; i <= n; ++i) { //暴力选择数字
        if (0 == inDegree[i] && 0 == mark[i]) {
            num[now] = i;
            mark[i] = 1;
            for (int j = 0; j < edg[i].size(); ++j) //遍历以i号点为起点的每条边
                --inDegree[edg[i][j]]; //全部入度数减1
            func(now + 1, edg);  

            //开始进行回溯
            mark[i] = 0;
            for (int j = 0; j < edg[i].size(); ++j) //遍历以i号点为起点的每条边
                ++inDegree[edg[i][j]];
        }
    }
}

int main()
{
    cin >> n >> m;
    vector<vector<int> > edg(n + 1, vector<int>());
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        ++inDegree[b];
        edg[a].emplace_back(b);
    }
    func(1, edg); //进行递归
    if (0 == r) cout << "Range!" << endl;
    return 0;
}