HDU 4612

2088 ワード

接続された無方向図に、追加後のブリッジを最小限に抑えるためにエッジを任意に追加します.縮点して木図の直径を求め、全体の強い連通成分-直径でいいです.
スタックを手動で拡張するには、その後C++で渡します.
初めてTarjanアルゴリズムを使って、ずっと図論を避けていたので、本当に勉強しても、難しくないです.コードを2回叩いて、2回目は思い切って1 Aになりました.やった問題のように、もう一度やる必要があります.
#pragma comment(linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<map>
using namespace std;

#define N 200010
#define M 1000010

struct NODE{
    int v,next;
}node[M*2];
bool vis[M];
int head[N];
int dp[N][2];
int dfn[N];
int low[N];
int cnt,ret,n,m;

void addEdge(int from,int to){
    node[cnt].next=head[from];
    node[cnt].v=to;
    head[from]=cnt++;
}

void Tarjan(int u){
    dp[u][0]=dp[u][1]=0;
    dfn[u]=low[u]=cnt++;
    for(int i=head[u];i!=-1;i=node[i].next){
        int j=node[i].v;
        if(vis[i>>1]) continue;
        vis[i>>1]=1;
        if(dfn[j]==0){
            Tarjan(j);
            ret+=low[j]>dfn[u];
            int temp = dp[j][0]+(low[j]>dfn[u]);
            if(temp>dp[u][0]){
                dp[u][1]=dp[u][0];
                dp[u][0]=temp;
            }else if(temp>dp[u][1]){
                dp[u][1]=temp;
            }
            low[u]=min(low[u],low[j]);
        }else{
            low[u]=min(low[u],dfn[j]);
        }
    }
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF&&n+m){
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        ret=cnt=0;
        for(int i=0;i<m;i++){
            int v,u;
            scanf("%d %d",&v,&u);
            addEdge(u,v);
            addEdge(v,u);
        }
        cnt=1;
        Tarjan(1);
        int temp=0;
        for(int i=1;i<=n;i++){
            temp=max(temp,dp[i][0]+dp[i][1]);
        }
        printf("%d
",ret-temp); } return 0; } /** test data imput 6 7 4 6 1 2 1 2 2 3 4 3 4 3 3 5 output 1 **/