专题五 拓扑排序/欧拉路

题解拓扑排序/欧拉路

[题目][A]

确定比赛名次

题目大意：

把N个队伍(1 <= N <= 500)按照M(0 <= M < 250000)个描述进行排名，让编号小的队伍尽量排在前面。
M描述如下：
P1 P2：P1赢了P2
有多个测试样例。

解题思路：

拓扑排序。利用kahn算法。
把队伍看做点，M所描述的关系为偏序关系，建立P1->P2的图，然后处理图，记下每个点的入度indegree[n]。找到入度为0的点然后压入优先队列（保证同一批的点按序号从小到大输出），然后优先级最高的出队，然后把从该点出发，有线段连接的端点的入度减一，然后再把入度为0的点压入优先队列。
时间复杂度O(n+m),空间复杂度O(1).

AC代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 500+5;
int graph[maxn][maxn];
int indegree[maxn];
int n,m;
struct cmp
{
    bool operator () (int &a,int &b)
    {
        return a > b;
    }
};
//priority_queue<int,vector<int>,cmp> q;
void toposort()
{
    int i;
    int temp;
    int cnt = 0;
    priority_queue<int,vector<int>,greater<int> >q;
    while(!q.empty()) q.pop();
    for(i = 1;i <= n;i++)
    {
        if(indegree[i] == 0) q.push(i);
    }
    while(!q.empty())
    {
        temp = q.top();
        cnt++;
        if(cnt == 1) printf("%d",temp);
        else printf(" %d",temp);
        q.pop();
        for(i = 1; i <= n; i++)
        {
            if(graph[temp][i])
            {
                indegree[i]--;
                if(indegree[i] == 0)
                    q.push(i);
            }
        }
    }
    printf("\n");
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int a,b;
    int i,j;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        memset(graph,0,sizeof(graph));
        memset(indegree,0,sizeof(indegree));
        for(i = 0;i < m;i++)
        {
            scanf("%d%d",&a,&b);
            graph[a][b] = 1;
        }
        for(i = 1;i <= n;i++)
        {
            for(j = 1;j <= n;j++)
            indegree[i] += graph[j][i];
        }
        toposort();
    }
    return 0;
}

[题目][D]

欧拉回路

题目大意：

给出n个点(1 < n < 1000)和m条边(1 < m < 1e6)，判断欧拉回路是否存在。
有多个测试样例，当n为0是输入结束。

解题思路：

无向欧拉图回路满足：
1、该图为连通图；
2、任一点的度数为偶数。
根据m条边的信息初始化图，保存每个点的度数到数组对应的位置，最后判断条件2.然后用bfs算法遍历图，根据最后遍历的标志量，来检查条件1.
时间复杂度O(m+n),空间复杂度O(1).

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
using namespace std;
int n,m;
const int maxn = 1000+5;
int graph[maxn][maxn];
int degree[maxn];
int bfs(int a)
{
    int flag[maxn];
    int i,temp;
    queue<int> p;
    for(i = 1;i <= n;i++) flag[i] = 0;//!!!
    p.push(a);
    flag[a] = 1;
    while(!p.empty())
    {
        temp = p.front();
        p.pop();
        for(i = 1;i <= n;i++)
        {
            if(graph[temp][i] && flag[i] == 0)
            {
                p.push(i);
                flag[i] = 1;
            }
        }
    }
    for(i = 1;i <= n;i++)
    {
        if(flag[i] == 0) return 0;
    }
    return 1;
}
int main()
{
    int i;
    int a,b;
    int sum;
    while(scanf("%d",&n) != EOF && n)
    {
        scanf("%d",&m);
        memset(graph,0,sizeof(graph));
        memset(degree,0,sizeof(degree));
        for(i = 0;i < m;i++)
        {
            scanf("%d%d",&a,&b);
            if(graph[a][b] == 0)
            {
                graph[a][b] = 1;
                graph[b][a] = 1;
                degree[a]++;
                degree[b]++;
            }
        }
        sum = 0;
        for(i = 1;i <= n;i++)
        {
            if(degree[i]% 2 == 1) sum++;
        }
        if(sum == 0 && bfs(a))
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}