小阳数数（暴力破解并查集）Java

谁践踏了优雅 2023-07-08 12:25 10阅读 0赞

## 题目链接 [小阳数数 ][Link 1]. ##

## 题目： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

## 分析： ##

由于是数字串，所以每个令牌最多包含十个数字，  
遍历所有令牌，有相同的就合并，直到不能合并为止

## AC代码： ##

import java.util.*;
    public class Main{ 
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int t=sc.nextInt();
    		while(t-->0){ 
    			int n=sc.nextInt();
    			ArrayList<HashSet<Character>> list=new ArrayList<HashSet<Character>>();
    			for(int i=0;i<n;i++){ 
    				HashSet<Character> set=new HashSet<Character>();
    				char [] c=sc.next().toCharArray();
    				int m=c.length;
    				for(int j=0;j<m;j++){ set.add(c[j]);}
    				list.add(set);
    			}
    			int len=Integer.MAX_VALUE;
    			for(int i=0;i<list.size();i++){ 
    				do{ 
    					len=list.size();
    					HashSet<Character> newset=new HashSet<Character>();
    					for(int j=i+1;list.size()>i+1&&j<list.size();j++){ 
    						for(char cc:list.get(j)){ 
    							if(list.get(i).contains(cc)){ 
    								newset.addAll(list.get(j));
    								list.remove(j);
    								j--;break;
    							}
    						}
    					}
    					list.get(i).addAll(newset);
    				}while(list.size()<len);
    			}
    			System.out.println(list.size());
    		}
    	}
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/3667/K
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200226155019610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200226155136769.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70