一本通基础 - 图论(一)

第一节 图的遍历

1.【例题】一笔画问题

题意:求无向图欧拉通路打印. 通路充要条件:G连通而且G仅有有两个奇点或无奇点. 无奇点 -> 必有欧拉回路 注意:要后存边,不然死循环.

void dfs(int x){ for(int i=1;i<=maxn;i++){ if(g[x][i]){ g[x][i] = g[i][x] = 0; dfs(i); } } ans[t++] = x; } void pri(){ for(int i=0;i<t-1;i++){ printf("%d ",ans[i]); } printf("%d\n",ans[t-1]); } int main(){ scanf("%d %d",&n,&m); memset(d,0,sizeof(d)); memset(g,0,sizeof(g)); for(int i=0;i<m;i++){ int u,v; scanf("%d%d",&u,&v); g[u][v] = g[v][u] = 1; d[u]++;d[v]++; maxn = max(maxn,u); maxn = max(maxn,v); } //从奇点开始dfs int st = 1; for(int i=1;i<=maxn;i++){ if(d[i] % 2){ st = i; break; } } t = 0; dfs(st); pri(); return 0; }

2.1375：骑马修栅栏(fence)

输出一条欧拉路径(每条边要走一遍) 和一笔画差不多,但是两个点中间可能有多条路,需要记录一下,然后打印路径要逆序.