`

poj 2230 Watchcow (欧拉回路+dfs)

阅读更多

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
4 5 1 2 1 4 2 3 2 4 3 4

 

Sample Output
1 2 3 4 2 1 4 3 2 4 1
 
          题目大意:给你一幅连通的图,要求从起点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;
}
 
0
0
分享到:
评论

相关推荐

    POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图

    题目"POJ-2870 Light Up"是一个经典的图论问题,主要涉及深度优先搜索(DFS)算法的运用。该问题要求点亮一个矩形区域内的所有障碍物,每个障碍物需要特定数量的灯光才能被照亮,且相邻的障碍物之间不能有空格。题目...

    POJ1691-Painting A Board 【拓扑+DFS】

    【标题】"POJ1691-Painting A Board 【拓扑+DFS】"是一个源自北京大学在线编程平台POJ的编程题目,它主要涉及到图论中的拓扑排序和深度优先搜索(DFS)算法。该题目的核心是解决一个与涂色相关的实际问题,通过运用...

    POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】

    提供的代码文件"POJ3009-Curling 2.0【DFS+Vector+剪枝】.cpp"和"POJ3009-Curling 2.0【DFS+回溯+剪枝】.cpp"应该分别展示了如何在实际编程中应用这些技术,而"POJ3009-Curling 2.0.doc"则可能是解题报告,详细阐述...

    西北工业大学POJ试题C++答案代码+课程设计

    "西北工业大学POJ试题C++答案代码+课程设计"这一标题表明了资源的主要内容,涉及两个核心部分:一是西北工业大学的编程竞赛(POJ,Problem Oriented Judge System)的C++解题代码,二是与这些题目相关的课程设计。...

    POJ3733-Changing Digits【DFS+强剪枝】

    【标题】"POJ3733-Changing Digits【DFS+强剪枝】"是一个来自北京大学在线评测系统POJ的编程题目,该题目主要涉及深度优先搜索(DFS)算法和强剪枝策略。在算法竞赛和编程挑战中,这类问题通常要求参赛者通过编写...

    欧拉回路题集

    ### 欧拉回路题集解析 #### 欧拉回路概念 欧拉回路(Eulerian Circuit)是指在一个无向图或有向图中,如果存在一条闭合路径,该路径通过每条边恰好一次,则这条路径称为欧拉回路。一个能够包含欧拉回路的图称为...

    POJ3373-Changing Digits【DFS+强剪枝】

    标题“POJ3373-Changing Digits【DFS+强剪枝】”涉及的是一个编程竞赛中的问题,这个问题在北大POJ(北京大学在线评测系统)平台上被提出。"Changing Digits"是一个算法挑战,而解决方案是通过深度优先搜索(DFS)...

    POJ1207-The 3n + 1 problem

    《POJ1207-The 3n + 1 problem》是北京大学在线编程平台POJ上的一道经典算法题目,其主要涉及的知识点是数论和动态规划。本题目的核心是解决著名的“Collatz Conjecture”问题,也被称为“3n+1猜想”。 3n+1猜想是...

    POJ PKU 必做题+部分难题1001-2500

    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 ...

    POJ1014-Dividing【DFS】【多重背包+二进制优化】

    在给出的文件列表中,“POJ1014-Dividing【多重背包+二进制优化】.cpp”和“POJ1014-Dividing【DFS】.cpp”很可能是两份不同的C++代码实现,分别展示了如何结合多重背包和二进制优化以及如何利用DFS来解决问题。...

    POJ1020-Anniversary Cake【有技巧的DFS】

    【标题】"POJ1020-Anniversary Cake【有技巧的DFS】"是一个源自北京大学在线编程平台POJ的编程题目,它涉及到深度优先搜索(DFS)算法的应用。这道题目要求参赛者通过编程解决一个有趣的问题,即在特定条件下如何...

    极角排序:POJ 1696(叉积+深搜)

    在POJ 1696这个编程题目中,很可能需要解决与极角排序相关的问题。POJ(Problem Online Judge)是一个在线的编程竞赛平台,它提供了许多编程题目供参赛者解决,以提升编程能力和算法理解。 描述中提到的“叉积+深搜...

    poj2488——dfs深度优先遍历

    poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历

    POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf

    ### POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf #### 一、题目背景及概述 本题属于图论中的经典问题之一,主要涉及无向图以及欧拉定理的应用。题目要求判断一个无向图是否满足欧拉路径(或欧拉回路)的...

    POJ1753-Flip Game

    两个解决方案的代码文件“POJ1753-Flip Game(BFS+bit).cpp”和“POJ1753-Flip Game(DFS+enum).cpp”分别实现了BFS和DFS策略。阅读这些代码可以帮助理解如何将理论转换为实际的程序实现。 五、文档说明 “POJ1753-...

    北大POJ初级-所有题目AC代码+解题报告

    【标题】"北大POJ初级-所有题目AC代码+解题报告" 涉及的知识点主要集中在编程、算法和在线判题系统方面。北京大学(Peking University, 简称PKU)的POJ(Peking University Online Judge)是一个为计算机科学爱好者...

    ACM常用算法及其相应的练习题.docx

    + poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...

    POJ3026-Borg Maze【BFS+Prim】

    《POJ3026-Borg Maze:BFS与Prim算法的应用解析》 在计算机科学领域,图论是解决问题的重要工具之一,而BFS(广度优先搜索)和Prim算法则是其中的两种经典算法。本篇文章将围绕北大POJ3026题目“Borg Maze”来探讨...

    POJ2186-Popular Cows【Tarjan+极大强连通分量+缩点】

    POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573

    acm pku spoj sgu 经典 图论题解题报告

    poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 isap 最快(ek会超时) poj2832 并查集边的...

Global site tag (gtag.js) - Google Analytics