Contents
http://poj.org/problem?id=2230
题目大意:
给定n个点和m条路,求从第1点出发每条路的两个方向都走一遍再回到原点(1)的路径。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
#include <cstring> #include <iostream> #include <algorithm> using namespace std;
const int N = 10010; const int M = 50010;
int n, m; int head[N]; bool vis[M * 2];
struct Edge{ int to; int next; }edge[2 * M];
void () { memset(head, -1, sizeof(head)); memset(vis, false, sizeof(vis)); }
void solve(int cur) { int k; for(k = head[cur]; ~k; k = edge[k].next){ if(!vis[k]){ vis[k] = true; solve(edge[k].to); printf("%dn", edge[k].to); } } }
int main() { freopen("input.txt", "r", stdin); int x, y; scanf("%d%d", &n, &m); init(); m <<= 1; for(int k = 0; k < m; k = k + 2){ scanf("%d%d", &x, &y); edge[k].to = y; edge[k].next = head[x]; head[x] = k;
edge[k + 1].to = x; edge[k + 1].next = head[y]; head[y] = k + 1; } solve(1); printf("1"); return 0; }
|
补:一开始没注意点的个数,开了个领接矩阵,直接超内存限制了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
#include <cstring> #include <iostream> #include <algorithm> using namespace std;
const int MAXN = 10010;
int n, m, k; int mp[MAXN][MAXN], ans[2 * MAXN];
void () { k = 0; memset(ans, 0, sizeof(ans)); memset(mp, 0, sizeof(mp)); }
void solve(int cur) {
for(int i = 0; i < MAXN; i++){ if(mp[cur][i]){ mp[cur][i] = 0; solve(i); ans[k++] = i; } } }
int main() { int x, y; while(scanf("%d%d", &n, &m) != EOF){ init(); for(int i = 0; i < m; i++){ scanf("%d%d", &x, &y); mp[x][y] = mp[y][x] = 1; } solve(1); ans[k++] = ans[0]; for(int i = 0; i < k; i++) printf("%dn", ans[i]); } return 0; }
|
近期评论