Mining Your Own Business

the # of escape shafts = number of non-degenerate bi-connected components (plus any "dead-ends") Amount of possibilities = count of all the non-articulation point vertices in each BCC....multiplied together

import java.awt.Point;
import java.util.*;
public class h {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new h().go();
	}
	private void go() {
		int cnum=0;
		while(true){
			cnum++;
			int n=in.nextInt();
			if(n==0)break;
			ArrayList<ArrayList<Integer>> a=new ArrayList<ArrayList<Integer>>();
			for(int i=0;i<n;i++){
				int s=in.nextInt()-1;
				int t=in.nextInt()-1;
				if(a.size()<=Math.max(s, t)+1)for(int j=a.size();j<=Math.max(s, t);j++)a.add(new ArrayList<Integer>());
				a.get(s).add(t);
				a.get(t).add(s);
			}
			ArrayList<ArrayList<Point>> bcc=biConnectedComponents(a);
			ArrayList<HashSet<Integer>> b=new ArrayList<HashSet<Integer>>();
			for(int i=0;i<a.size();i++)b.add(new HashSet<Integer>());
			for(int i=0;i<bcc.size();i++)for(Point p:bcc.get(i)){
				b.get(p.x).add(i);
				b.get(p.y).add(i);
			}
			int ans=0;
			ArrayList<Integer> cnts=new ArrayList<Integer>();
			for(int i=0;i<bcc.size();i++){
				int other=0;
				int leaves=0;
				HashSet<Integer> checked=new HashSet<Integer>();
				for(Point p:bcc.get(i)){
					if(checked.contains(p.x))continue;
					checked.add(p.x);
					if(b.get(p.x).size()>1)other++;
					else leaves++;
					if(checked.contains(p.y))continue;
					checked.add(p.y);
					if(b.get(p.y).size()>1)other++;
					else leaves++;
				}
				if(other<=1){
					ans++;
					cnts.add(leaves);
				}
			}
			long ans2=1;
			for(int i:cnts)ans2*=i;
			if(bcc.size()==1){
				ans=2;
				ans2=b.size()*(long)(b.size()-1)/2L;
			}
			System.out.printf("Case %d: %d %d\n", cnum,ans,ans2);
		}
	}
	public ArrayList<ArrayList<Point>> biConnectedComponents(ArrayList<ArrayList<Integer>> in){
		int[][] t=new int[3][in.size()];//order,link,various indices
		Stack<Point> s=new Stack<Point>();
		ArrayList<ArrayList<Point>> out=new ArrayList<ArrayList<Point>>();
		HashSet<Point>u=new HashSet<Point>();
		for(int i=0;i<in.size();i++)if(t[0][i]==0)dfs(i,in,out,s,t,u);
		if(!s.isEmpty())out.add(new ArrayList<Point>(s));
		return out;
	}
	private void dfs(int i,ArrayList<ArrayList<Integer>> in,ArrayList<ArrayList<Point>> out,Stack<Point> s ,int[][] t, HashSet<Point> u) {
		t[1][i]=t[0][i]=++t[2][0];
		int min=t[1][i];
		for(int j:in.get(i)){
			if(u.contains(new Point(j,i)))continue;//if already traversed this edge in the other direction
			u.add(new Point(i,j));
			s.push(new Point(i,j));
			if(t[0][j]==0)dfs(j,in,out,s,t,u);//don't  recurse on previously visited nodes
			min=Math.min(min,t[1][j]);
			if(t[0][i]<=t[1][j]){
				ArrayList<Point> al=new ArrayList<Point>();
				while(al.size()==0||al.get(al.size()-1).x!=i)al.add(s.pop());
				out.add(al);
			}
		}
		t[1][i]=min;
	}
}
//Mining Your Own Business
//bcc
//dag