本文共 1303 字，大约阅读时间需要 4 分钟。
题目链接：
题目意思：
在无向连通图中图中找一个经过边数最多的环。
解题思路：
从任意一点直接DFS，不用回溯，注意构成环的话至少有3条边。
因为任意一个最大环，一定可以搜到。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #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)|1using 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;}
转载地址：http://thigo.baihongyu.com/