欧拉回路--输出欧拉回路的路径

//有向or无向均可，重边

step1:从u开始，找到与他相连的v，放入栈，删除(u,v)这条边，然后从v开始

step2:当有一点没有与他相连的点时，放入path，然后从stack取栈顶继续开始找点删边。

最后记得把栈里的点放到path中。

path倒序输出

//需要先找到起点

//邻接表法，适合稀疏图

#include

#include

#include

#include

#include

using namespacestd;

const int maxn =100 +5;

vector mp[maxn];

multiset mps[maxn];//支持重边

int n,m;

void get_path(int s)

{

stack stk;

vector path;

int u = s,v;

stk.push(u);

int cnt =0;

for(;;)

{

if(!mps[u].empty())

{

v = *mps[u].begin();

stk.push(v);

mps[u].erase(mps[u].begin());

// mps[v].erase(mps[v].find(u));//无重边的无向图，要删除（v，u）

// mps[v].erase(mps[v].lower_bound(u));//有重边的无向图，删除(v,u)

u = v;

}

else {

path.push_back(u);

stk.pop();

u = stk.top();

cnt ++;

}

if(cnt ==n)break;

}

while (!stk.empty()) {

path.push_back(stk.top());

stk.pop();

}

for(int i = path.size() -1;i >= 0;i -- )cout << path[i] <<" ";cout <<endl;//倒序输出！

}

int main()

{

int u,v;

while (scanf("%d%d",&n,&m) != EOF) {

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

scanf("%d%d",&u,&v);

mp[u].push_back(v);

mps[u].insert(v);

// mp[v].push_back(u);//无向图

// mps[v].insert(u);

}

int s =1;

get_path(s);

}

return0;

}

//邻接矩阵法，适合稠密图

#include

#include

#include

#include

#include

using namespace std;

const int maxn = 100 + 5;

int mp[maxn][maxn];

int deg[maxn];

int in[maxn],out[maxn];//有向图

vector path;

stack stk;

int n,m;

void get_path(int s)

{

int u = s,v;

int cnt = 0;

stk.push(u);

for(;;)

{

//if(deg[u]){//无向

if(out[u]){//有向

for (int i = 1; i <= n; i ++) {//设结点从1开始

if(mp[u][i]){

mp[u][i] --;//mp[i][u] --;//通过邻接矩阵计数可以解决重边的问题

// deg[u] --;deg[i] --;//无向

out[u] -- ;in[i] --;//有向

u = i;

stk.push(u);

break;

}

}

}

else{

path.push_back(stk.top());

stk.pop();

u = stk.top();

cnt ++;

}

if(cnt == n) break;

}

while (!stk.empty()) {

path.push_back(stk.top());

stk.pop();

}

for (int i = path.size() - 1; i >= 0; i --) {

printf("%d ",path[i]);

}printf("\n");

}

int main()

{

int u,v;

while (scanf("%d%d",&n,&m) != EOF) {

memset(mp, 0, sizeof(mp));

// memset(deg, 0, sizeof(deg));

memset(in, 0, sizeof(in));

memset(out, 0, sizeof(out));

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

scanf("%d%d",&u,&v);

mp[u][v] ++;//mp[v][u] ++;//无向

// deg[u] ++;deg[v] ++;//无向

out[u] ++,in[v] ++;//有向

}

int s = 1;

get_path(s);

}

return 0;

}