hdu4612 無向圖中任意添加一條邊後使橋的數量最少 / 無向圖縮點+求樹的直徑
題意如上，含有重邊（重邊的話，倆個點就可以構成了邊雙連通）。
先縮點成樹，在求數的直徑，最遠的連起來，剩下邊（橋）的自然最少。這裡學習了樹的直徑求法：第一次選任意起點U，進行bfs，到達最遠的一個點v（level最深）該點必然是樹的直徑的一個端點，,再從該點出發，bfs，到最深的一點，該點深度就是直徑。（證明：先假設u，是直徑上一點，S,T是直徑的端點，設v!=t,則有（V,U)+(U,S)>(T,U)+(U,S),矛盾，故t=v；若u不是直徑上一點，設u到直徑上的一點為x，同理易證。
最後 縮點後樹的邊-直徑即可。
再說說這次，哎，先是爆棧，沒有在C++申請空間。。。 無向圖的tarjian太不熟練了！很久沒敲了。。。。
注意點：無向圖求邊雙連通，縮點，可以這樣：
法1：必需用前向星來保存邊，然後標記訪問邊（同時標記反向邊）的方法來處理。這樣，重邊的話，就在字自然在一個邊通分量中了。（要求邊數可以用數組存下），這樣不用！=-father來判斷。
法2，重邊視為單邊（只有倆個點不連通），不標記邊，多一個參數father，在返祖邊更新我的時候，加判斷！=father。
#pragma comment(linker, "/STACK:10240000000000,10240000000000") //申請空間
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxv=300010;
int dfn[maxv];int low[maxv];int visited[maxv];
int ins[maxv];stacksta;int scc[maxv];
int times=0;int block=0;
int n,m;
int minn(int a,int b)
{
if(a<=b)return a;
return b;
}
int nume=0;int e[2000500][2];int head[maxv];
void inline adde(int i,int j) //原圖
{
e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++;
e[nume][0]=i;e[nume][1]=head[j];head[j]=nume++;
}
int nume2=0;int newg[2000500][2];int head2[maxv];
void inline adde2(int i,int j) //新圖
{
newg[nume2][0]=j;newg[nume2][1]=head2[i];head2[i]=nume2++;
newg[nume2][0]=i;newg[nume2][1]=head2[j];head2[j]=nume2++;
}
bool marke[2001000]; //標記邊的訪問
void tarjan(int u)
{
dfn[u]=low[u]=++times;
ins[u]=1;
sta.push(u);
for(int i=head[u];i!=-1;i=e[i][1])
{
int child=e[i][0];
if(marke[i])continue; //注意放在這裡，否則下面的會更新，起不了作用
if(visited[child]==0)
{
visited[child]=1;
marke[i]=marke[i^1]=1; //標記雙向
tarjan(child);
low[u]=minn(low[u],low[child]);
}
else if(ins[child])
{
low[u]=minn(dfn[child],low[u]);
}
}
if(low[u]==dfn[u]) //同一個邊雙連通
{
block++;
int cur;
do
{
cur=sta.top();
ins[cur]=0;
sta.pop();
scc[cur]=block;
}while(cur!=u);
}
}
void rebuild()
{
for(int i=1;i<=n;i++) //遍歷所有邊，來重新建圖，若在同一個邊雙連通中，則有邊。
{
for(int j=head[i];j!=-1;j=e[j][1])
{
int ch=e[j][0];
if(scc[i]!=scc[ch])
adde2(scc[i],scc[ch]);
}
}
}
int lev[maxv];
void bfsgetlev(int ss) //BFS分層
{
memset(lev,0,sizeof(lev));
memset(visited,0,sizeof(visited));
queueq;
q.push(ss);
visited[ss]=1;
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=head2[cur];i!=-1;i=newg[i][1])
{
int vv=newg[i][0];
if(!visited[vv])
{
lev[vv]=lev[cur]+1;
q.push(vv);
visited[vv]=1;
}
}
}
return ;
}
void init()
{
block=times=0;nume=0;nume2=0;
memset(marke,0,sizeof(marke));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(visited,0,sizeof(visited));
memset(head,-1,sizeof(head));
memset(head2,-1,sizeof(head2));
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
init();
int a,b;
for(int i=0;imaxx)
{
maxx=lev[i];
froms=i;
}
}
bfsgetlev(froms); //最遠點（直直徑的一個端點）
for(int i=1;i<=block;i++)
{
if(lev[i]>maxx)
{
maxx=lev[i];
}
}
ans=block-1-maxx;
printf("%d\n",ans);
}
return 0;
}
