POJ 3895 Cycles of Lanes (dfs)_poj dfs 有环_左眼皮跳跳~的博客-程序员宅基地

Description

Each of the M lanes of the Park of Polytechnic University of Bucharest connects two of the N crossroads of the park (labeled from 1 to N). There is no pair of crossroads connected by more than one lane and it is possible to pass from each crossroad to each other crossroad by a path composed of one or more lanes. A cycle of lanes is simple when passes through each of its crossroads exactly once.
The administration of the University would like to put on the lanes pictures of the winners of Regional Collegiate Programming Contest in such way that the pictures of winners from the same university to be on the lanes of a same simple cycle. That is why the administration would like to assign the longest simple cycles of lanes to most successful universities. The problem is to find the longest cycles? Fortunately, it happens that each lane of the park is participating in no more than one simple cycle (see the Figure).

Input

On the first line of the input file the number T of the test cases will be given. Each test case starts with a line with the positive integers N and M, separated by interval (4 <= N <= 4444). Each of the next M lines of the test case contains the labels of one of the pairs of crossroads connected by a lane.

Output

For each of the test cases, on a single line of the output, print the length of a maximal simple cycle.

Sample Input

Sample Output

Source

Southeastern European Regional Programming Contest 2009

题意就是求最大的环包含点的个数，但是有一个麻烦的地方，就是dfs 到一个点时，怎么快速知道与这个点相连点呢？

后来我知道了 vector 开一个vector数组保存就行了，接下来就是代码了，细节在代码中

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 5000

vector<int>q[N];

int vis[N];
int n,m;
int ans;

void dfs(int a,int pos)
{
    int i;
    vis[a]=pos;

    for(i=0;i<q[a].size();i++)
     {
         int x=q[a][i];

         if(!vis[x])
            dfs(x,pos+1);    
         else
            if(vis[a]-vis[x]+1>ans)  //例如环 1 2 3 4 1 ,vis[1]=1,vis[4]=4,下一次4与
                                    //1相连，但是已经vis[1],所以环的大小 vis[4]-vis[1]+1
               ans=vis[a]-vis[x]+1;
     }
}

int main()
{
    int i,t;
    scanf("%d",&t);

    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(vis,0,sizeof(vis));
        int x,y;
        
        for(i=1;i<=n;i++)  //记得清空上次的数据
            q[i].clear();
        
        while(m--)
        {
            scanf("%d%d",&x,&y);
            q[x].push_back(y);  //q[x]存与x的临边
            q[y].push_back(x);  //同理
        }

        ans=0;
       for(i=1;i<=n;i++)
        if(!vis[i])  //因为一个点就会出现一次，即使两个环有共同边，
                     //那么在公共边那个分叉点还是会分别进行dfs的
            dfs(i,1);
                    //不加下面会错
        if(ans<=2)//一个环需要3个点，但是我郁闷了，如果没有环的话
                  //怎么会有vis[x]已经标记了呢？（此时ans=0啊）难道有数据类似
                  // a b   b a  (⊙o⊙)…
            ans=0;
        printf("%d\n",ans);
    }
    return 0;
}

dfs还不是很熟，但是有事缠身，哎以后一定好好补补dfs

今天听说一种叫做邻接表的东西，居然用一维数组存储与任意起点相关联的所有边的信息，感觉很神奇，不怎么好懂，刚刚入门o(╯□╰)o，也可以用到这个提上

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 4500

int ans,vis[N],head[N];
int n,m,num;

struct stud{
int to,next;
}e[N*2];

void build(int u,int v)
{
    e[num].to=v;
    e[num].next=head[u];
    head[u]=num;
    num++;
}

void dfs(int x,int pos)
{
    vis[x]=pos;
    int i;

    for(i=head[x];i!=-1;i=e[i].next)
    {
        if(vis[e[i].to])
            ans=max(ans,vis[x]-vis[e[i].to]+1);
        else
            dfs(e[i].to,pos+1);
    }
}
int main()
{
    int i,j,v,u,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));

        num=0;
        while(m--)
        {
            scanf("%d%d",&v,&u);
            build(v,u);
            build(u,v);
        }
        memset(vis,0,sizeof(vis));
        ans=0;

        dfs(1,0);

        if(ans<3) ans=0;

        printf("%d\n",ans);
    }
    return 0;
}

本文链接：https://blog.csdn.net/u014737310/article/details/38510571

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

实录 | 平安人寿资深算法工程师姚晓远：对话生成模型的探析与创新_PaperWeekly的博客-程序员宅基地

1 月 10 日（周四）晚 8 点，平安人寿智能平台团队资深算法工程师姚晓远在 PaperWeekly 直播间为大家带来了对话生成模型的探析与创新主题分享，并且介绍了平安..._平安寿险外派算法

[Python密码学]--凯撒加密及换位加密法_有哪些变换位置的加密方法_许沐白的博客-程序员宅基地

凯撒加密法所谓凯撒加密是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。message = 'hello world! Nice to meet you.'key = 13mode = 'encrypt' # encrypt or decrypt 选择加密或解..._有哪些变换位置的加密方法

MySQL笔记9——表的创建之约束条件_数据库建表约束条件不为0_kerongw的博客-程序员宅基地

文章目录0、约束定义（constraint）1、常见约束2、非空约束(not null)3、唯一性约束(unique)4、主键约束(primary key)①、主键相关术语②、主键作用？③、主键分类④、MySQL提供主键自增(auto_increment)5、外键约束(foreign key)①、外键约束术语②、主键作用？0、约束定义（constraint）约束是为了限制表中的数据，保证添加到数据表中的合法性、有效性、完整性！凡是不符合约束的数据，插入时就会失败！1、常见约束非空约束(not nu_数据库建表约束条件不为0

Windows下，将tomcat注册为服务启动_windows tomcat service.bat_可乐cc呀的博客-程序员宅基地

Windows下，将tomcat注册为服务启动文章目录Windows下，将tomcat注册为服务启动前言一、找到 service.bat文件二、注册总结前言提示：这里可以添加本文要记录的大概内容：例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。提示：以下是本篇文章正文内容，下面案例可供参考一、找到 service.bat文件确认你的tomcat\bin 目录下,可以找到 service.bat 文件。如果_windows tomcat service.bat

不同框架接口自动化的优劣_常用自动化部署工具优缺点对比jenkins_萧木易的博客-程序员宅基地

POSTMAN缺点：1、只使用单一API场景测试2、无法实现脚本间串联调用3、无法和CI/CD工具结合4、断言方法比较复杂5、无法查看执行结果6、无法做到数据分离优点：1、上手容易，调试方便2、适合快速测试、一次性测试JMETER缺点：1、上手较难，调试和问题定位不方便2、可移植性低，修改成本大3、可以查看执行结果，但不直观，加入html插件可以规避优点：1、可以实现脚本间串联调用2、可以多种断言方式3、有多种函数支持4、支持和jenkins工具集成5、可以做数据_常用自动化部署工具优缺点对比jenkins

树莓派3B+鸿蒙镜像的烧录_树莓派安装鸿蒙os_魔动山霸的博客-程序员宅基地

因工作需要要在树莓派上搭载鸿蒙系统，步骤如下：在ubuntu18上安装环境：# 安装必要的包sudo apt updatesudo apt install -y binutils git git-lfs gnupg flex bison gperf build-essential \ zip curl zlib1g-dev gcc-multilib g++-multilib libc6-dev-i386 \ lib32n_树莓派安装鸿蒙os

随便推点

Codeforces Gym 101190 NEERC 2016 B. Binary Code_gjghfd的博客-程序员宅基地

题解#includeusing namespace std;#define N 500010#define M 4000000vectorc[N];vectora[N<<1],g[M];int num,nx[N<<1][2],w[N<<1],w2[N<<1];int i,j,k,n,m,p,pos[N],pr[N<<1],sf[N<<

Android下面打印进程函数调用堆栈(dump backtrace)的方法__unwind_backtrace_蓝白天际线的博客-程序员宅基地

1. 为什么要打印函数调用堆栈？打印调用堆栈可以直接把问题发生时的函数调用关系打出来，非常有利于理解函数调用关系。比如函数A可能被B/C/D调用，如果只看代码，B/C/D谁调用A都有可能，如果打印出调用堆栈，直接就把谁调的打出来了。不仅如此，打印函数调用堆栈还有另一个好处。在Android代码里，函数命名很多雷同的，虚函数调用，几个类里的函数名相同等，即使用source insight工具看也未必...__unwind_backtrace

python if 语句--小任务2_python 如果列表为空则打印消息,否则删除_Awesome╮（﹀＿﹀）╭的博客-程序员宅基地

5-8以特殊方式跟管理员打招呼：创建一个至少包含5个用户名的列表，且其中一个用户名为'admin'。想象你要编写代码，在每位用户登录网站后都打印一条问候消息。遍历用户名列表，并向每位用户打印一条问候消息。·如果用户名为'admin'，就打印一条特殊的问候消息，如“Helloadmin,wouldyouliketoseeastatusreport?”。·否则，打印一条普通的问候消息，如“HelloEric,thankyouforlogginginagain”。u..._python 如果列表为空则打印消息,否则删除

MAC下的Sublime Text关闭自动更新提示，关闭更新检查，适用于Sublime 3和Sublime 4_mac 禁用sublime text提示_MateCloud微服务的博客-程序员宅基地

一、现象描述每次打开sublime text总会弹出一个更新的提示框，需要点击取消才能进入到下一步，增加了一些不必须的困扰，如下图所示：如何关闭呢？二、关闭方法打开sublime text窗口，通过快捷键⌘+,打开编辑窗口，在里面输入"update_check":false,注意：update_check的属性前后都要有一个逗号。如下图所示：保存即可。再次打开sublime text，烦人的更新提示就没有了。收工。..._mac 禁用sublime text提示

Python实现手写体数字图片识别+GUI界面+画板数字识别_pythonlaodi的博客-程序员宅基地

__pycache__文件夹是Python自动生成的，详细了解https://blog.csdn.net/yitiaodashu/article/details/79023987其他各个文件在之后部分会依次介绍图片识别版本：python3.6tensorflow 1.13.1（一定要安装1.几版本，不要安装2.几）运行时可能有很多warning，不影响运行结果此部分大多程序参考《TensorFlow实战Google深度学习框架》这里使用的是基于全连接层网络结构的神经网络，对数字识..._python实现手写体数字图片识别+gui界面+画板数字识别

50个php开发工具_南三方的博客-程序员宅基地

PHP是使用最为广泛的开源服务器端脚本语言之一，当然PHP并不是速度最快的，但它却是最常用的脚本语言。这里有50个有益的PHP工具，可以大大提高你的编程工作：调试工具Webgrind Xdebug Gubed PHP Debugger DBG PHP_Debug PHP_Dyn MacGDBp 测试和优化工具PHPUnit SimpleTes