poj-3895-Cycles of Lanes 簡單DFS

題目意思：   在無向連通圖中圖中找一個經過邊數最多的環。   解題思路：   從任意一點直接DFS，不用回溯，注意構成環的話至少有3條邊。   因為任意一個最大環，一定可以搜到。   代碼：

<SPAN style="COLOR: #330033; FONT-SIZE: 18px">#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;
}



</SPAN>