tarjan缩点+树的直径
https://www.byvoid.com/blog/scc-tarjan/ 讲tarjian比较好
http://blog.csdn.net/u010638776/article/details/9472605 借鉴了这里
#include<iostream> #include<cstdio> #include<cstdio> #include<queue> #pragma comment(linker, "/STACK:1024000000,1024000000") //扩栈 using namespace std; #define maxn 210000 #define maxm 2100000 int n,m; int head[maxn],v[maxm],next[maxm],cnt; int head1[maxn],v1[maxm],next1[maxm],cnt1; int dfn[maxn],low[maxn],step; int sta[maxn],top; int ID[maxn],IdNum; int vis[maxn]; int r; void Init() { memset(vis,0,sizeof(vis)); memset(head1,-1,sizeof(head1)); memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); IdNum=top=step=cnt1=cnt=0; } void add1(int a,int b) { v1[cnt1]=b; next1[cnt1]=head1[a]; head1[a]=cnt1++; } void add(int a,int b) { v[cnt]=b; next[cnt]=head[a]; head[a]=cnt++; } void tarjan(int u,int pre) //pre为前一个点 { dfn[u]=low[u]=++step; sta[++top]=u; vis[u]=1; int k=0; for(int i=head[u];~i;i=next[i]) { int to=v[i]; if(!dfn[to])//如果没有进过栈 { tarjan(to,u);//继续找 low[u]=min(low[u],low[to]); } else { if(to==pre)//如果是前一个点 { if(k)//考虑了重边的可能 low[u]=min(low[u],dfn[to]); k++;//无向边是建2条边 } else if(vis[to]) low[u]=min(low[u],dfn[to]); } } if(dfn[u]==low[u]) { IdNum++; int x; do { x=sta[top--]; vis[x]=0; ID[x]=IdNum;//表示在同一个强连通分量 }while(u!=x); } } int bfs(int x) { queue<int> q; int dis[maxn]; int end; memset(dis,-1,sizeof(dis)); q.push(x); dis[x]=0; while(!q.empty()) { int u=q.front(); q.pop(); r=dis[u]; end=u; for(int i=head1[u];~i;i=next1[i]) { int to=v1[i]; if(dis[to]==-1) { dis[to]=dis[u]+1; q.push(to); } } } return end; } int main() { int x,y; while(~scanf("%d%d",&n,&m)&&n+m) { Init(); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(x==y) continue; add(x,y); add(y,x); } tarjan(1,-1); // cout<<IdNum<<endl; for(int i=1;i<=n;i++)// 缩点建边 for(int j=head[i];~j;j=next[j]) { int to=v[j]; if(ID[i]!=ID[to]) add1(ID[i],ID[to]); } bfs(bfs(1));//2次bfs找树的直径 printf("%d\n",IdNum-1-r); } return 0; }