[BZOJ]1023: [SHOI2008]cactus仙人掌圖

Time Limit: 1 Sec??Memory Limit: 162 MB

Description

　　如果某個無向連通圖的任意一條邊至多只出現在一條簡單回路（simple cycle）里，我們就稱這張圖為仙人掌圖（cactus）。所謂簡單回路就是指在圖上不重復經過任何一個頂點的回路。

?

　　舉例來說，上面的第一個例子是一張仙人圖，而第二個不是——注意到它有三條簡單回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同時出現在前兩個的簡單回路里。另外，第三張圖也不是仙人圖，因為它并不是連通圖。顯然，仙人圖上的每條邊，或者是這張仙人圖的橋（bridge），或者在且僅在一個簡單回路里，兩者必居其一。定義在圖上兩點之間的距離為這兩點之間最短路徑的距離。定義一個圖的直徑為這張圖相距最遠的兩個點的距離。現在我們假定仙人圖的每條邊的權值都是1，你的任務是求出給定的仙人圖的直徑。

Input

　　輸入的第一行包括兩個整數n和m（1≤n≤50000以及0≤m≤10000）。其中n代表頂點個數，我們約定圖中的頂點將從1到n編號。接下來一共有m行。代表m條路徑。每行的開始有一個整數k（2≤k≤1000），代表在這條路徑上的頂點個數。接下來是k個1到n之間的整數，分別對應了一個頂點，相鄰的頂點表示存在一條連接這兩個頂點的邊。一條路徑上可能通過一個頂點好幾次，比如對于第一個樣例，第一條路徑從3經過8，又從8返回到了3，但是我們保證所有的邊都會出現在某條路徑上，而且不會重復出現在兩條路徑上，或者在一條路徑上出現兩次。

Output

　　只需輸出一個數，這個數表示仙人圖的直徑長度。

Sample Input

　（樣例1）

　　15 3
　　9 1 2 3 4 5 6 7 8 3
　　7 2 9 10 11 12 13 10
　　5 2 14 9 15 10

　（樣例2）
　　10 1
　　10 1 2 3 4 5 6 7 8 9 10

Sample Output

　（樣例1）

　　8

　（樣例2）
　　9

HINT

　　對第一個樣例的說明：如圖，6號點和12號點的最短路徑長度為8，所以這張圖的直徑為8。

?

【注意】使用Pascal語言的選手請注意：你的程序在處理大數據的時候可能會出現棧溢出。如果需要調整棧空間的大小，可以在程序的開頭填加一句：{$M 5000000}，其中5000000即指代棧空間的大小，請根據自己的程序選擇適當的數值。

Solution

　　對仙人掌做一次dfs得到一棵dfs樹，用f[i]表示i到子樹中的點的最長距離，對于橋，我們直接更新f[i]=max(f[j]+1)，并更新答案；對于環上的邊，我們對每個環都統計一次答案并把信息匯總到環中深度最小的點上，匯總信息比較容易，考慮如何在環內統計答案，先把環拆成鏈，復制一份接在后面，然后對每個點i統計點i在環上向前的環大小一半的個數的點，即ans=max(f[i]+f[j]+dis(i,j))（dis(i,j)<=環的大小/2），這樣就可以用單調隊列可以維護，總復雜度O(n)。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{int x;char c;while((c=getchar())<'0'||c>'9');for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0';return x;
}
#define MN 50000
struct edge{int nx,t;}e[MN*4+5];
int h[MN+5],en,d[MN+5],l[MN+5],cnt,fa[MN+5],f[MN+5],ans,a[MN*2+5],an,q[MN*2+5],ql,qr;
inline void ins(int x,int y)
{e[++en]=(edge){h[x],y};h[x]=en;e[++en]=(edge){h[y],x};h[y]=en;
}
void tj(int x)
{int i,j;d[x]=l[x]=++cnt;for(i=h[x];i;i=e[i].nx)if(e[i].t!=fa[x]){if(!d[e[i].t])fa[e[i].t]=x,tj(e[i].t);l[x]=min(l[x],l[e[i].t]);if(l[e[i].t]>d[x])ans=max(ans,f[x]+f[e[i].t]+1),f[x]=max(f[x],f[e[i].t]+1);}for(i=h[x];i;i=e[i].nx)if(fa[e[i].t]!=x&&d[e[i].t]>d[x]){for(an=0,j=e[i].t;j!=x;j=fa[j])a[++an]=f[j];a[++an]=f[x];for(j=1;j<=an;++j)a[j+an]=a[j];for(j=ql=1,qr=0;j<=an<<1;++j){while(ql<=qr&&j-q[ql]>an>>1)++ql;if(ql<=qr)ans=max(ans,a[j]+a[q[ql]]+j-q[ql]);while(ql<=qr&&a[j]-j>=a[q[qr]]-q[qr])--qr;q[++qr]=j;}for(j=1;j<an;++j)f[x]=max(f[x],a[j]+min(an-j,j));}
}
int main()
{int n,m,k,x,y;n=read();m=read();while(m--)for(k=read(),x=read();--k;x=y)ins(x,y=read());tj(1);printf("%d",ans);
}