Watchcow
Time Limit : 6000/3000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 2
Special Judge
Problem Description
Bessie's been appointed the new watch-cow for the farm. Every night, it's her job to walk across the farm and make sure that no evildoers are doing any evil. She begins at the barn, makes her patrol, and then returns to the barn when she's done.
If she were a more observant cow, she might be able to just walk each of M (1 <= M <= 50,000) bidirectional trails numbered 1..M between N (2 <= N <= 10,000) fields numbered 1..N on the farm once and be confident that she's seen everything she needs to see. But since she isn't, she wants to make sure she walks down each trail exactly twice. It's also important that her two trips along each trail be in opposite directions, so that she doesn't miss the same thing twice.
A pair of fields might be connected by more than one trail. Find a path that Bessie can follow which will meet her requirements. Such a path is guaranteed to exist.
Input
* Line 1: Two integers, N and M.
* Lines 2..M+1: Two integers denoting a pair of fields connected by a path.
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 Input
Sample Output
题目大意:给你一幅连通的图,要求从起点1开始走,要经过每条边刚好两次,并且最终回到1起点。其实就是再每条边基础上加多一条不同方向的边,这样再一个dfs就搞定了,很简单。
代码:
#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;
}
分享到:
相关推荐
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
Catenyms poj hoj 欧拉回路输出路径
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ初级-所有题目AC代码+解题报告
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类