阿祁的部落格

Uva 10765 Doves and bombs 解題心得 ( 題目 )

解題概念:BCC(雙連通分量)

解題方法:這題需要利用O(N)求出移除任一點的連通塊數量，如果是N次DFS會TLE，因此下方利用Tarjan's BCC algorithm計算，答案=該點位於的BCC數量，時間複雜度=O(N)。

//Author:En Chi Tsung(欉恩祁)

//Date:2022/04/06

import java.util.*;

import java.io.*;

public class uva10765 {

    public static int pre=0,t=0;

    public static int[] dfs=new int[10005];

    public static int[] low=new int[10005];

    public static boolean[] ins=new boolean[10005];

    public static boolean[] vis=new boolean[10005];

    public static Pair[] ans;

    public static HashSet<Integer> hs=new HashSet<>();

    public static Stack<Pair> st=new Stack<>();

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static ArrayList<ArrayList<Integer>> e=new ArrayList<>();

    public static void main(String[] args) throws Exception{

        String[] in;

        int n,m;

        while(true) {

            in=br.readLine().split(" ");

            n=Integer.parseInt(in[0]);

            m=Integer.parseInt(in[1]);

            if(n==0&&m==0)break;

            Solve(n,m);

        }

    }    

    

    public static void Solve(int n,int m) throws Exception{

        String[] in;

        int a,b;

        init(n);

        while(true) {

            in=br.readLine().split(" ");

            a=Integer.parseInt(in[0]);

            b=Integer.parseInt(in[1]);

            if(a==-1&&b==-1)break;

            e.get(a).add(b);

            e.get(b).add(a);

        }

        for(int i=0;i<n;i++) {

            if(!vis[i]) {

                tarjan(i,-1);

            }

        }

        for(int i=0;i<n;i++) {

            if(ans[i].y==0) {

                ans[i].y=1;

            }

        }

        Sort();

        for(int i=0;i<m;i++) {

            bw.write(ans[i].x+" "+ans[i].y+"\n");

        }

        bw.write("\n");

        bw.flush();

    }

    

    public static void tarjan(int x,int pre) {

        dfs[x]=low[x]=t++;

        ins[x]=vis[x]=true;

        Pair o;

        for(int i:e.get(x)) {

            if(i==pre)continue;

            if(!vis[i]) {

                st.push(new Pair(x,i));

                tarjan(i,x);

                low[x]=Math.min(low[x],low[i]);

                if(dfs[x]<=low[i]) {

                    while(true) {

                        o=st.pop();

                        add(o.y);

                        ins[o.y]=false;

                        if(o.x==x&&o.y==i) {

                            add(o.x);

                            break;

                        }

                    }

                    hs.clear();

                }

            }

            else if(ins[i]) {

                low[x]=Math.min(low[x],dfs[i]);

                st.push(new Pair(x,i));

            }

        }

        ins[x]=false;



    }

    

    public static void Sort() {

        Arrays.sort(ans,new Comparator<Pair>() {

            public int compare(Pair f,Pair s) {

                if(f.y==s.y)return f.x-s.x;

                return s.y-f.y;

            }

        });

    }

    

    public static void add(int x) {

        if(!hs.contains(x)) {

            ans[x].y++;

            hs.add(x);

        }

    }

    

    public static void init(int n) {

        t=0;

        Arrays.fill(ins,false);

        Arrays.fill(vis,false);

        ans=new Pair[n];

        e.clear();

        st.clear();

        for(int i=0;i<n;i++) {

            e.add(new ArrayList<Integer>());

        }

        for(int i=0;i<n;i++) {

            ans[i]=new Pair(i,0);

        }

    }

}



class Pair{

    int x,y;

    Pair(int a,int b){

        x=a;

        y=b;

    }

}