- 在线时间
- 9 小时
- 最后登录
- 2012-10-15
- 注册时间
- 2010-3-30
- 听众数
- 3
- 收听数
- 0
- 能力
- 0 分
- 体力
- 80 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 53
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 53
- 主题
- 0
- 精华
- 0
- 分享
- 0
- 好友
- 4
升级   50.53% 该用户从未签到
- 自我介绍
- 数学的一个懵懂者。
|
#include <stdio.h>
. ?* V0 o# C; i; [- }, Z#include <string.h>
0 O. n0 }- ^ }2 Q. Y1 Bstruct stack0 w, L9 @; V$ ]
{int top , node[210];} f; //顶点的堆栈
7 c G; [+ p3 ]: uint a[201][201]; //图的邻接矩阵
8 A( r* ^% P* Oint n;5 O3 C) p! V. b5 O9 `$ E
void dfs(int x) //图的深度优先遍历* F6 _9 Y! L1 o7 l+ X! O' p7 ]4 e
{int i;
- B( B8 s8 e5 y ~4 |! s, A7 Cf.top ++; f.node[f.top] = x;) N+ N% E" d8 T
for (i = 1; i <= n; i ++)
" S: p7 F0 u! z2 _4 Q8 Jif (a[i][x] > 0)
1 L! e# w h3 O3 Z { a[i][x] = 0; a[x][i] = 0; //删除此边7 r) i8 v" [( `" x
dfs(i);
# ~) B+ u6 _2 g& ]& ]: O+ Ybreak; }
% H( _# K/ t4 n, I" T" ?/ p}
1 G+ g* T3 l8 @void Euler(int x) //欧拉路算法
1 ]; K Z/ V- q{int i , b;
5 P( j7 l* o5 C. Pf.top = 0; f.node[f.top] = x; //入栈
\% p. {5 f8 A8 Y+ |( G `while (f.top >= 0)& G; E0 U& k9 h% o6 J! I. I) G+ Y1 h2 J
{b = 0;7 ~! H7 D8 }: I- ~0 ?( R1 z# _ ?& W
for (i = 1; i <= n; i ++)
2 n/ e) W- p; u* `) dif (a[f.node[f.top]][i] > 0)
4 T5 X. A% @% x2 O; f) w; z{b = 1; break;}- \" Y7 S: h; P1 q
if (b == 0) //如果没有点可以扩展,输出并出栈
; p7 \8 S" D( D7 T2 W( ~{ printf("%d " , f.node[f.top]);) u+ T% n8 T: \$ t) ]
f.top --;}
5 v+ h' i; X5 }else {f.top --; dfs(f.node[f.top+1]);} //如果有,就DFS4 b: p5 X2 B: U% m4 G1 j
}
# a4 l: m7 s* k}
1 y/ f; @: r2 k( x1 r: E- _int main()
. [5 ~5 Y; A% b( ?" e{
! ?3 ` {1 v* Lint m , s , t , num , i , j , start;; e- P/ ^1 }5 ^7 w, N9 x: e8 Q
//input
2 E7 b$ Z5 f" S1 L( h, Rscanf("%d %d" , &n , &m); //n顶点数 m边数
) h. T7 s' z* C2 E/ imemset(a , 0 , sizeof(a));+ x: K+ c1 N7 `' g+ O' N
for (i = 0; i < m; i ++)
) h1 c1 J+ o4 a5 K' G{printf("innput s,t");
" X* e i& [8 d3 N* D scanf("%d %d" , &s , &t);
' z4 m7 q- j$ q. G9 \0 s* l. [ a[s][t] = 1; a[t][s] = 1;
@ H7 [+ u4 y9 T1 Y5 X( T8 J}
4 D: w6 D' e" n9 [4 q //判断是否存在欧拉回路% t6 l3 |* a c" @$ N
s = 0; start = 1;
+ o; n+ z: b2 H4 s for (i = 1; i <= n; i ++)
' o: ?1 C( s n, x2 O+ r) Z5 v{num = 0;
$ H: w$ U; K8 a7 N& Qfor (j = 1; j <= n; j ++)$ D, p% O$ y8 p: Z' w7 q
num += a[i][j];
; M% N" A' i1 y6 I if (num % 2 == 1)
0 a& [& h2 J) b1 N# Q6 R{start = i; s ++;}/ I: K0 }: a0 A9 Z
}
& x5 w. \! ]7 s3 Dif ((s == 0) || (s == 2)) % K( H0 K3 o8 Q; K% v3 W
Euler(start);
V$ K3 ]" U: c# D else printf("No Euler path\n");- \" F, q" m6 y
getchar(); getchar();
C, |; q; R# B. wreturn 0; } |
|