ITKeyword,专注技术干货聚合推荐

注册 | 登录

poj-3895-Cycles of Lanes 简单DFS

cc_again 分享于 2013-07-18

推荐:POJ3895 Cycles of Lanes,DFS

很简单的搜索题,DFS和BFS都可以。 /******************************************************************************* # Author : Neo Fung # Email : neos

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题目链接:

http://poj.org/problem?id=3895

题目意思:

在无向连通图中图中找一个经过边数最多的环。

解题思路:

从任意一点直接DFS,不用回溯,注意构成环的话至少有3条边。

因为任意一个最大环,一定可以搜到。

代码:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;

int ans;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
bool flag[5500];
struct Edge
{
   int v;
   struct Edge * next;
}*head[555500],edge[555500];
int n,m,cnt;
int num[4500];

void add(int a,int b)
{
   cnt++;
   edge[cnt].v=b,edge[cnt].next=head[a];
   head[a]=&edge[cnt];
}

void dfs(int cur,int hav)
{
   struct Edge *p=head[cur];
   flag[cur]=true;
   num[cur]=hav;
   while(p)
   {
      if(flag[p->v]) //下一步已经访问过了,说明有环
      {
         if(hav+1-num[p->v]>ans) //往回走的话就是2
            ans=hav+1-num[p->v];
      }
      else
         dfs(p->v,hav+1);
      p=p->next;
   }
  // num[cur]=0; //不需要回溯
   //flag[cur]=false;
}

int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d",&n,&m);
      memset(head,NULL,sizeof(head));
      memset(flag,false,sizeof(flag));
      memset(num,0,sizeof(num));
      cnt=0;
      for(int i=1;i<=m;i++)
      {
         int a,b;
         scanf("%d%d",&a,&b);
         add(a,b),add(b,a);

      }
      num[1]=0;
      ans=0;
      dfs(1,0);
      if(ans < 3) //凑成环的话,至少要三条边
         ans = 0;
      printf("%d\n",ans);
   }
   return 0;
}





题目链接: http://poj.org/problemid=3895 题目意思: 在无向连通图中图中找一个经过边数最多的环。 解题思路: 从任意一点直接DFS,不用回溯,注意构成环的话至少有3条边。 因为任意一个最大

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。