Cycles of Lanes --HOJ 11877

时间：2010-09-21 来源：勇泽

1、题目类型：图论、最大环、DFS。

2、解题思路：（1）建立图的连接矩阵；（2）类似于求解强连通分量（Trajan算法）利用时间戳DFS最大环。

3、注意事项：注意宏定义常量的大小，预防MLE。

4、实现方法:

#include<iostream>
using namespace std;
#define MyMax 4445

int n,m,ans;
int dfn[MyMax];
bool g[MyMax][MyMax];

void DFS(int v)
{
    for(int i=1;i<=n;i++)
    {
        if(g[v][i])
        {
            if(!dfn[i])
            {    
                g[i][v]=0;
                dfn[i]=dfn[v]+1;
                DFS(i);
            }
            else
            {
                int tmp=dfn[v]-dfn[i]+1;
                if(tmp>ans)
                    ans=tmp;
                g[i][v]=0;
            }
        }
    }
}

int main()
{
    int i,a,b,T;
    cin>>T;    
    while(T--)
    {
        ans=0;
        memset(g,0,sizeof(g));
        memset(dfn,0,sizeof(dfn));
        cin>>n>>m;        
        for(i=0;i<m;i++)
        {
            cin>>a>>b;
            g[a][b]=g[b][a]=1;
        }
        for(i=1;i<=n;i++)
        {
            if(!dfn[i])
            {
                dfn[i]=1;
                DFS(i);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}