拓扑排序 - hdu 1285（普通和优先队列优化）

2017-09-12 19:50:58

writer:pprp

最近刚开始接触拓扑排序，拓扑排序适用于：无圈图的顶点的一种排序，

用来解决有优先级别的排序问题，比如课程先修后修，排名等。

主要实现：用矩阵来储存图，用indegree数组记录每个顶点的入度，

从入度为0的开始，每次删除该入度为0的点，然后修改其他顶点的入度，

在进行查找入度为0的顶点，循环下去就可以

题意如下：给你n个队伍，m个优先顺序，让你输出总的排名的优先顺序。

代码如下:

/*

@theme:拓扑排序 hdu 1285

@writer:pprp

@declare: accepted

@begin:19:00

@end:19:47

@error:

*/

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int maxn = ;

bool G[maxn][maxn];

int ans[maxn];

int indegree[maxn];//存取入度

int n, m;

void init()

{

    memset(indegree,,sizeof(indegree));

    memset(ans,,sizeof(ans));

    memset(G,,sizeof(G));

}

void toposort()

{

    for(int i =  ; i <= n ; i++)

    {

        for(int j =  ;j <= n ;j++)

        {

            if(G[i][j])

                indegree[j]++;

        }

    }

    //应该从入度为0的开始

    for(int i = ; i <= n;i++)

    {

        int k = ;

        while(indegree[k]!=)

            k++;

        ans[i] = k;

        //删除根节点

        indegree[k] = -;

        for(int j = ; j <= n; j++)

        {

            if(G[k][j])

                indegree[j]--;

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    int x, y;

    while(cin >> n >> m)

    {

        init();

        for(int i =  ; i < m ;i++)

        {

            cin >> x >> y;

            G[x][y] = ;

        }

        toposort();

        for(int i = ; i < n; i++)

            cout << ans[i] << " ";

        cout << ans[n] << endl;

    }

    return ;

}

分析当前的：

每次删掉一个点以后就要遍历全部的点找到入度为0的点，其实入度为0的点只可能出现在改动之后的点，

所以采用了优先队列，记录下来当前的入度为0的点，将其输出或者储存下来以后，改变由该点指向的点的入度

从这些改动的点中看看有没有入度为0的点，如果有的话，那就将其入队列，直到队列为空，或者记录的已经被删除的点的个数是所有的点

那么退出完成程序

优化代码如下：

/*

@theme:拓扑排序 hdu 1285

@writer:pprp

@declare: accepted

@begin:19:59

@end:20:38

@error:注意保持头脑清醒

*/

#include <iostream>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cstdio>

using namespace std;

const int maxn = ;

int indegree[maxn];

int n, m, x, y;

bool G[maxn][maxn];

void topsort()

{

    priority_queue<int,vector<int>,greater<int> > pq;

    for(int i = ; i <= n; i++)

        for(int j = ; j <= n; j++)

            if(G[i][j])

                indegree[j]++;

    for(int i = ; i <= n; i++)

        if(indegree[i] == )

            pq.push(i),indegree[i] = -1;

    int counter = ;

    while(!pq.empty())

    {

        int v = pq.top();

        pq.pop();

        if(counter != n)

        {

            cout << v << " ";

            counter++;

        }

        else

        {

            cout << v << endl;

            break;

        }

        for(int i = ; i <= n;i++)

        {

            if(G[v][i] == )

            {

                indegree[i]--;

                if(indegree[i] == )

                    pq.push(i),indegree[i] = -1;

            }

        }

    }

    if(counter != n)

        cerr << "graph has a cycle." << endl;

}

void init()

{

    memset(indegree,,sizeof(indegree));

    memset(G,,sizeof(G));

}

int main()

{

    freopen("in.txt","r",stdin);

    while(cin >> n >> m)

    {

        init();

        for(int i =  ; i < m ; i++)

        {

            cin >> x >> y;

            G[x][y] = ;

        }

        topsort();

    }

    return ;

}

巴特西

拓扑排序 - hdu 1285（普通和优先队列优化）

最新文章

热门文章