?
Input * Line 1: Two integers, N and M.?
Output * Lines 1..2M+1: A list of fields she passes through, one per line, beginning and ending with the barn at field 1. If more than one solution is possible, output any solution.?
Sample Input4 5 1 2 1 4 2 3 2 4 3 4
?
Sample Output1 2 3 4 2 1 4 3 2 4 1? ????????? 题目大意:给你一幅连通的图,要求从起点1开始走,要经过每条边刚好两次,并且最终回到1起点。其实就是再每条边基础上加多一条不同方向的边,这样再一个dfs就搞定了,很简单。 链接:http://poj.org/problem?id=2230 代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <vector> using namespace std; struct edge { bool vis; int end, next; }a[100005]; int res[100005], adj[100005]; //adj是第一条的编号 int n, m, cnt, ant; void init() { int i; for(i = 0; i <= 2*m; i++) { a[i].vis = false; } memset(adj, -1, sizeof(adj)); ant = cnt = 0; } void dfs(int cur, int id) { int i; for(i = adj[cur]; i != -1; i = a[i].next) { if(!a[i].vis) { a[i].vis = true; dfs(a[i].end, i); } } if(id != -1) res[ant++] = a[id].end; } int main() { int i, x, y; while(scanf("%d %d", &n, &m) != EOF) { init(); for(i = 0; i < m; i++) { scanf("%d %d", &x, &y); /// *****建边***** a[cnt].end = y; a[cnt].next = adj[x]; adj[x] = cnt++; a[cnt].end = x; a[cnt].next = adj[y]; adj[y] = cnt++; /// *************** } dfs(1, -1); printf("1\n"); for(i = ant-1; i >= 0; i--) { printf("%d\n", res[i]); } } return 0; }?