poj-3895-Cycles of Lanes 简单DFS

题目链接：

题目意思：

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

解题思路：

从任意一点直接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;

}

秒客网

poj-3895-Cycles of Lanes 简单DFS

相关文章