Hdu 4612 Warm up (双连通缩点+树的直径)

一时失言乱红尘 2022-08-10 14:55 114阅读 0赞

题意：有N 个点，M条边，加一条边，求割边最少。（有重边）

思路：先求双连通分量，缩点形成一个生成树，然后求这个的直径，割边-直径即是答案

#pragma comment(linker, "/STACK:1024000000,1024000000")
    #include <cstdio>
    #include <cstring>
    #include <stack>
    #include <queue>
    #include <vector>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int INF=0x3f3f3f3f;
    
    const int nPoint=200010;
    const int nEdges=2000010;
    vector<int>G[nPoint];
    
    class BCC
    {
    public:
    	struct Edge{
    		int from, to, next;
    		bool cut;  //是否为桥
    	}edge[nEdges];
    
    	int e,id,n;
    	int head[nPoint],dfn[nPoint], low[nPoint];
    	int bridgetop;
    	int colornum, top; //双连通分量数,栈顶
    	int color[nPoint],Stack[nPoint];
    	bool iscut[nPoint];  //该点是否为割点
    	int bri_cut;    //桥的数目
    
    	void Add (int u, int v){
    		Edge E={u,v,head[u],false};
    		edge[ e ] = E;
    		head[u] = e++;
    	}
    
    	void Tarjan (int u, int pre)
    	{
    		dfn[u]=low[u]=++id;
    		Stack[++top]=u;
    		int child=0, flag=1;
    		
    		for (int i=head[u]; ~i; i=edge[i].next)
    		{
    			int v=edge[i].to;
    			//if (v == pre) continue; //重边算一条的写法
    			if (flag && v==pre)
    			{//重边有效的写法
    				flag = 0; 
    				continue;
    			}
    			if (!dfn[v])
    			{
    				child++;
    				Tarjan(v,u);
    				low[u] = min(low[u], low[v]);
    				if (low[v] >= dfn[u])
    				{
    					iscut[u] = true;  //是割点
    					if (low[v]>dfn[u])
    						edge[i].cut = edge[i^1].cut = true;  //是桥
    				}
    			}
    			else low[u] = min(low[u], dfn[v]);
    		}
    		if (child == 1 && pre<0) //树根
    			iscut[u] = false;
    		if (low[u] == dfn[u])
    		{
    			colornum++;
    			do
    			{
    				color[ Stack[top] ] = colornum;
    			}while(Stack[top--] != u);
    		}
    	}
    
    	void Init (int _n)
    	{
    		n=_n;
    		memset(head, -1, sizeof(head));
    		memset(dfn, 0, sizeof(dfn));
    		memset(iscut, 0, sizeof(iscut));
    		memset(color, -1, sizeof(color));
    		bridgetop =e=id= 0;
    		top = colornum = 0;
    	}
    
    	void Deal ()
    	{
    		int i;
    		for (i=1; i<=n; i++) if (!dfn[i])
    			Tarjan(i, -1);
    		for (i=0; i<=colornum; i++)
    			G[i].clear();
    		bri_cut = 0;
    		for (i=0; i<e; i+=2)
    		{//建新图
    			int u = color[edge[i].from];
    			int v = color[edge[i].to];
    			if (u != v)
    				G[u].push_back(v), G[v].push_back(u);
    			bri_cut += edge[i].cut;
    		}
    	}
    }ob;
    
    int n,m;
    int dis[nPoint];
    
    int BFS (int u)
    {
        for (int i = 0;i<=n;i++)dis[i] = INF;
        dis[u] = 0; 
        queue<int>q;
        q.push(u);
        int pos = u, d = 0;
        while (!q.empty()){
            u = q.front(); q.pop();
            for(int i=0;i<G[u].size();i++)
            {
                int v = G[u][i];
                if(dis[v] > dis[u]+1)
                {
                    dis[v] = dis[u]+1;
                    q.push(v);
                    if(dis[v] > d)d=dis[v] , pos = v;
                }
            }
        }
        return pos;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	while (scanf("%d%d",&n,&m), m+n)
    	{
    		ob.Init(n);
    		int u,v;
    		while (m--)
    		{
    			scanf("%d %d",&u,&v);
    			ob.Add(u,v);
    			ob.Add(v,u);
    		}
    		ob.Deal();
    		u=BFS(1);
    		v=BFS(u);
    		printf("%d\n",ob.bri_cut - dis[v]);
    	}
    	return 0;
    }