HDU 3172 및 집합 + trie 트 리 검색
제목: n 개의 관 계 를 주 고 u 와 v 의 집합 에서 요소 의 개 수 를 묻는다.
사고방식: 간단 하고 집합 을 찾 으 면 됩 니 다. 다만 이것 이 주 는 문자열 은 비교적 옹졸 합 니 다. 우 리 는 trie 트 리 로 찾 으 면 됩 니 다. 조작 은 간단 합 니 다. 그리고 문 제 를 내 는 사람 이 여러 그룹 을 설정 하고 여러 그룹 으로 입력 해 야 한 다 는 것 을 주의 하 세 요. 감탄 할 수 밖 에 없습니다. WA 는 두 번, org ~ ~ ~
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int maxn=400010;
int f[maxn],num[maxn];
int find1(int x){
if(x==f[x]) return f[x];
int t=f[x];
f[x]=find1(f[x]);
return f[x];
}
void unite(int a,int b){
int aa=find1(a);
int bb=find1(b);
if(aa==bb) return ;
f[aa]=bb;
num[bb]+=num[aa];
}
struct Trie{
Trie *next[70];
int v;
};
Trie *root;
char str1[30],str2[30];
void creatTrie(char *str,int idx){
int len=strlen(str);
Trie *p=root,*q;
for(int i=0;i<len;i++){
int id=str[i]-'A';
if(p->next[id]==NULL){
q=(Trie *)malloc(sizeof(Trie));
q->v=0;
for(int j=0;j<70;j++)
q->next[j]=NULL;
p->next[id]=q;
}
p=p->next[id];
}
p->v=idx;
}
int findtrie(char *str){
int len=strlen(str);
Trie *p=root;
for(int i=0;i<len;i++){
int id=str[i]-'A';
p=p->next[id];
if(p==NULL) return 0;
}
return p->v;
}
int dealtrie(Trie *T){
if(T==NULL) return 0;
for(int i=0;i<70;i++) if(T->next[i]!=NULL) dealtrie(T->next[i]);
free(T);
return 0;
}
int main(){
int T,n;
while(scanf("%d",&T)!=-1){
while(T--){
scanf("%d",&n);
for(int i=0;i<=2*n;i++){
f[i]=i;num[i]=1;
}
int k=1;
root=(Trie *)malloc(sizeof(Trie));
for(int i=0;i<70;i++) root->next[i]=NULL;
for(int i=0;i<n;i++){
scanf("%s%s",str1,str2);
int ans1=findtrie(str1);
int ans2=findtrie(str2);
if(ans1==0) creatTrie(str1,k++);
if(ans2==0) creatTrie(str2,k++);
int id1=findtrie(str1);
int id2=findtrie(str2);
unite(id1,id2);
int ans=find1(id1);
printf("%d
",num[ans]);
}
dealtrie(root);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.