# poj-3895-Cycles of Lanes 简单DFS

cc_again 分享于 2013-07-18

```#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;
int n,m,cnt;
int num[4500];

{
cnt++;
}

void dfs(int cur,int hav)
{
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(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);

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

```

×
• 登录
• 注册

×