poj 3895 Cycles of Lanes(DFS找最大环)

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

题目大意：

一个无向图，找出包含顶点个数的环，输出最大顶点个数；

思路：

简单搜索

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

int vis[N],n,m;
int Max;
vector <int> graph[N];//vector存储相连接的点

void DFS(int v,int d)
{
    vis[v]=d;
    int size=graph[v].size();
    for(int i=0;i<size;i++)
    {
        if(!vis[graph[v][i]])//
            DFS(graph[v][i],d+1);
        else
        {
            if(vis[v]-vis[graph[v][i]]+1>Max)
                Max=vis[v]-vis[graph[v][i]]+1;
        }
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int s,e;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)
            graph[i].clear();
        
        for(int j=0;j<m;j++)
        {
            scanf("%d%d",&s,&e);
            graph[s].push_back(e);
            graph[e].push_back(s);
            //双向建图
        }
        Max=0;
        memset(vis,0,sizeof(vis));
        for(int k=1;k<=n;k++)
        {
            if(!vis[k])
                DFS(k,1);//DFS找环,
        }
        if(Max<=2)//Max<=2即不存在环
            Max=0;
        printf("%d\n",Max);
    }
    return 0;
}