欧拉回路构造.cpp

本人参加ACM竞赛使用的一些算法模板

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/******************************************************
*   构造欧拉回路（有向图），前置条件是
*   必须存在欧拉回路，输出是点s出发回到点s
*   的一条欧拉回路。邻接表实现。
*   (poj    2230    Watchcow)
*******************************************************/

int const MAXN = 100100;
struct node
{//边结点
    int v, u;
    int num;
    node(){}
    node(int v_, int u_)
    {
		v = v_;
		u = u_;
	}
};
node edge[2 * MAXN];//邻接表
int N, M;//点数、边数
int visit[MAXN];//记录每个点被经过的次数
int stk[MAXN], cnt;//栈
struct cmp
{//对边进行排序比较成为邻接表
	bool operator () (node a, node b)
	{
        if (a.v == b.v) return a.u < b.u;
	    return a.v < b.v;
	}
};
int path(int v)
{//找环算法
    int w, i;
    for(; ; v = w)
    {
        for (i = lower_bound(edge, edge + M, node(v, -1), cmp() ) - edge;
			i < 2 * M && edge[i].v == v; ++i)
        {
        	if (visit[edge[i].num] < 2)
			{//该点经过了两次。
				break;
			}
		}
        if (i >= M || edge[i].v != v)
		{
			break;
		}
        stk[cnt++] = v;
        w = edge[i].u;
        ++visit[edge[i].num];
    }
   	return v;
}
int res[MAXN];
void Eulur(int v)
{
 	printf("%d\n",v);
    while((path(v) == v) && cnt)
	{//每找到一个新环，把新环加入到旧环中去。
        v = stk[--cnt];
        printf("%d\n", v);
    }
}

int main()
{
    scanf("%d %d",&N, &M);
    for (int i = 0; i < M; ++i)
    {//建图
        int p, q;
        visit[i] = 0;
        scanf("%d %d",&p, &q);
        edge[i].v = p;
		edge[i].u = q;
		edge[i].num = i;
        edge[i + M].v = q;
		edge[i + M].u = p;
		edge[i + M].num = i;
    }
    M *= 2;
    sort (edge, edge + M, cmp() );
    cnt = 0;
    Eulur(1);
    system("pause");
    return 0;
}