【图论】拓扑排序

文章目录

拓扑排序的概念等不赘述了。

拓扑排序的方法

代码实现

拓扑排序（Topological Sorting）_神奕的博客-CSDN博客_拓扑排序

代码上我是照着他的入门的

题目

2367 – Genealogical tree (poj.org)
模板题，构建一个图，再排序输出即可。

oj不支持C++11,得把auto换成迭代器…

#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;

#define N 1000
queue<int>output;
class Graph
{
public:
    Graph(int v)//顶点个数初始化，new邻接表，把入度集合全部初始化为0
        
    {
        _v = v;
        _adj = new list<int>[v];//new一个有v个顶点的邻接表
        _indegree.resize(v, 0);//初始化入度集合
    }
    ~Graph()
    {
        delete[] _adj;
    }
    void addEdge(int val, int w)//值为val的点指向w
    {
        _adj[val].push_back(w);
        _indegree[w]++;
    }
    bool topological_sort()
    {
        for (int i=1;i<_indegree.size();i++)//入队结点其实还存在一层映射
        {
            if (!_indegree[i])
            {
                _q.push(i);
            }
        }
        int count = 0;
        while (!_q.empty())
        {
            int v = _q.front();
            _q.pop();
            output.push(v);
            count++;
            //更新入度集合，把入度为0的点入队
            list<int>::iterator it = _adj[v].begin();
            for (;it!=_adj[v].end();it++)
            {
                _indegree[*it]--;
                if (!_indegree[*it])
                {
                    _q.push(*it);
                }
            }
        }
        if (count<_v)//图有回路
        {
            return false;
        }
        else
        {
            return true;
        }
    }
private:
    int _v;//顶点个数
    list<int>* _adj;//邻接表
    queue<int>_q;//维护入度为0的顶点的集合
    vector<int> _indegree;//记录每个顶点的入度
};

int main()
{
    int n;
    cin >> n;
    Graph g(n+1);
    for (int i = 1; i <= n; i++)
    {
        int x;
        while (cin >> x)
        {
            if (x == 0)
            {
                break;
            }
            g.addEdge(i, x);
        }
    }
    g.topological_sort();
    bool flag = 1;
    while (!output.empty())
    {
        int x = output.front();
        output.pop();
        if (flag)
        {
            cout << x;
            flag = 0;
        }
        else
        {
            cout << " " << x;
        }
    }
    return 0;
}