题目链接:Cycles of Lanes
思路:
用一个a数组记录第i个点出现在那几条边上,b数组记录每条边相连的两个点,num数组记录每个点被连的次数,dis记录搜索时从起点到该点的距离,输入记录完后每次都从还没有记录距离的点开始搜索直到搜到环,记录最长距离;
代码:
#include<algorithm> #include<iostream> #include<cstring> #include<stdio.h> #include<math.h> #include<string> #include<stdio.h> #include<queue> #include<stack> #include<map> #include<deque> using namespace std; struct edge { int f,t; }; int a[4500][105]; edge b[4500]; int num[4500]; int vis[4500]; int dis[4500]; int maxx,n,m; void dfs(int index,int step) { if(dis[index]) { int t=step-dis[index]; if(maxx<t) { maxx=t; } step=dis[index]; } else dis[index]=step; for(int i=0;i<num[index];i++) { if(!vis[a[index][i]]) { vis[a[index][i]]=1; int d=((index==b[a[index][i]].f)?b[a[index][i]].t:b[a[index][i]].f); dfs(d,step+1); } } } int main() { int i,j,test,x,y; scanf("%d",&test); while(test--) { scanf("%d%d",&n,&m); memset(num,0,sizeof(num)); memset(dis,0,sizeof(dis)); for(i=0;i<m;i++) { scanf("%d%d",&x,&y); b[i].f=x; b[i].t=y; vis[i]=0; a[x][num[x]]=i; num[x]++; a[y][num[y]]=i; num[y]++; } maxx=0; for(i=1;i<=n;i++) { if(!dis[i]) dfs(1,1); } printf("%d\n",maxx); } return 0; }
原文:https://www.cnblogs.com/KasenBob/p/10890622.html