求二叉樹的寬度，F - Warm up - hdu 4612(縮點+求樹的直徑)

題意：有一個無向連通圖，現在問添加一條邊后最少還有幾個橋

分析：先把圖縮點，然后重構圖為一棵樹，求出來樹的直徑即可，不過注意會有重邊，構樹的時候注意一下

***********************************************************************

#pragma?comment(linker,?"/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using?namespace?std;

const?int?MAXN?=?2e5+5;

struct?Edge{int?v,?vis,?next;}e1[MAXN*10],?e2[MAXN*10];
int?Head1[MAXN],?Head2[MAXN],?cnt[3],?fa[MAXN];
void?AddEdge(Edge?e[],?int?Head[],?int?u,?int?v,?int?k)
{
????e[?cnt[k]?].v?=?v;
????e[?cnt[k]?].vis?=?0;
????e[?cnt[k]?].next?=?Head[u];
????Head[u]?=?cnt[k]++;
}

struct?node{int?u,?step;};
node?BFS(node?s,?int?k)
{
????queue<node>?Q;
????Q.push(s);

????while(Q.size())
????{
????????s?=?Q.front();Q.pop();

????????for(int?j=Head2[s.u];?j!=-1;?j=e2[j].next)
????????{
????????????node?q?=?s;
????????????q.u?=?e2[j].v;

????????????if(e2[j].vis?!=?k)
????????????{
????????????????e2[j].vis?=?e2[j^1].vis?=?k;
????????????????q.step++;
????????????????Q.push(q);
????????????}
????????}

????}

????return?s;
}

int?dfn[MAXN],?low[MAXN],?Index;
int?belong[MAXN],?bnt;
int?Stack[MAXN],?top;

void?InIt(int?N)
{
????cnt[1]?=?cnt[2]?=?Index?=?bnt?=?top?=?0;
????for(int?i=1;?i<=N;?i++)
????{
????????Head1[i]?=?Head2[i]?=?-1;
????????dfn[i]?=?0;
????????fa[i]?=?0;
????}
}
void?Tarjan(int?u)
{
????int?v;

????low[u]?=?dfn[u]?=?++Index;
????Stack[++top]?=?u;

????for(int?j=Head1[u];?j!=-1;?j=e1[j].next)
????{
????????v?=?e1[j].v;
????????if(e1[j].vis?==?false)
????????{
????????????e1[j].vis?=?e1[j^1].vis?=?true;
????????????if(?!dfn[v]?)
????????????{
????????????????Tarjan(v);
????????????????low[u]?=?min(low[u],?low[v]);
????????????}
????????????else
????????????????low[u]?=?min(low[u],?dfn[v]);
????????}
????}

????if(low[u]?==?dfn[u])
????{
????????++bnt;
????????do
????????{
????????????v?=?Stack[top--];
????????????belong[v]?=?bnt;
????????}
????????while(u?!=?v);
????}
}
int?main()
{
????int?N,?M;

????while(scanf("%d%d",?&N,?&M),?N+M)
????{
????????int?i,?j,?u,?v;

????????InIt(N);

????????while(M--)
????????{
????????????scanf("%d%d",?&u,?&v);
????????????AddEdge(e1,?Head1,?u,?v,?1);
????????????AddEdge(e1,?Head1,?v,?u,?1);
????????}

????????Tarjan(1);

????????for(i=1;?i<=N;?i++)
????????for(j=Head1[i];?j!=-1;?j=e1[j].next)
????????{
????????????v?=?e1[j].v;
????????????u?=?belong[i],?v?=?belong[v];
????????????if(u?>?v?&&?fa[v]?!=?u)
????????????{
????????????????fa[v]?=?u;
????????????????AddEdge(e2,?Head2,?u,?v,?2);
????????????????AddEdge(e2,?Head2,?v,?u,?2);
????????????}
????????}

????????node?s;
????????s.u?=?1,?s.step?=?0;

????????s?=?BFS(s,?1);
????????s.step?=?0;
????????s?=?BFS(s,?2);

????????printf("%d\n",?bnt-s.step-1);
????}

????return?0;?

}

?