股票推荐系统,并查集
package org.example;
import java.util.*;
public class Main {
private static int query(List<Integer> parent,int index){//查询根节点
if(parent.get(index)!=index){
int tmp=query(parent,parent.get(index));
parent.set(index,tmp);
}
return parent.get(index);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q=in.nextInt();
int gcount=0;
Map<String,int[]> pMap=new HashMap<>();//记录每个用户的关注的股票数以及其中一支股票的id
Map<String,Integer> stockIdMap=new HashMap<>();//记录每个股票的id
ArrayList<Integer> count=new ArrayList<>();//记录每个集合的元素数
ArrayList<Integer> parent=new ArrayList<>();//记录每个股票的父节点
for(int k=0;k<q;k++){
int ops=in.nextInt();
if(ops==1){//注册
String name=in.next();
if(!pMap.containsKey(name)){
pMap.put(name,new int[2]);
}
int[] cur=pMap.get(name);
int n=in.nextInt();
cur[0]=n;
int root=0;
for(int i=0;i<n;i++){
String stock=in.next();
if(!stockIdMap.containsKey(stock)){
stockIdMap.put(stock,gcount++);
parent.add(gcount-1);
count.add(1);
}
int stockId=stockIdMap.get(stock);
if(i==0){
cur[1]=stockId;
root=query(parent,stockId);
}else{
int aRoot=query(parent,stockId);
if(aRoot!=root){
parent.set(aRoot,root);
count.set(root,count.get(root)+count.get(aRoot));
}
}
}
}else{//查询
String name=in.next();
if(!pMap.containsKey(name)){
System.out.println("error");
continue;
}
int[] cur=pMap.get(name);
int root=query(parent,cur[1]);
System.out.println(count.get(root)-cur[0]);
}
}
}
}