题意：
给一个边权均为1的无向图，求图中的最大环。
分析：
tarjan算法一般用来强连通分量，它依次访问图中的各个强连通分量，这题要求最大环，而环也是强连通分量的一部分，所以可以在每个点访问其他点时修改时间戳，达到每个环上时间戳连续的目的，这样当访问到一个栈中节点时就能直接更新最大环了。根据同样的思路，即使边权任意，，也可求最大环或最小环。
代码：
//poj 3895//sep9#include <iostream>#include <vector>#include <stack>using namespace std;const int maxN=4500;vector<int> g[maxN];stack<int> s;int dfn[maxN],low[maxN],ins[maxN],belong[maxN];int n,m,ans,t,cnt;void tarjan(int fa,int u){dfn[u]=low[u]=++t;ins[u]=1;s.push(u);for(int i=g[u].size()-1;i>=0;–i){int v=g[u][i];if(fa==v)continue;if(!dfn[v]){int tmp=t;tarjan(u,v);t=tmp;low[u]=min(low[u],low[v]);}else if(ins[v]==1){low[u]=min(low[u],dfn[v]);ans=max(ans,dfn[u]-dfn[v]+1);}}int k;if(low[u]==dfn[u]){++cnt;do{k=s.top();s.pop();ins[k]=0;belong[k]=cnt;}while(dfn[k]!=low[k]);}}int main(){int cases;scanf("%d",&cases);while(cases–){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)g[i].clear();while(m–){int x,y;scanf("%d%d",&x,&y);g[x].push_back(y);g[y].push_back(x);}t=cnt=ans=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(ins,0,sizeof(ins));while(!s.empty()) s.pop();tarjan(-1,1);printf("%d\n",ans);}return 0;}
诚实是人生绝妙的法宝。虽然对人诚实，
