hdu 5923 (집합 유지보수 블록)
5746 단어 데이터 구조
magic tree 의 모든 점 에서 뿌리 까지 의 집합 을 유지 합 니 다. (또한 원 그림 의 생 성 트 리 입 니 다. 이 점 의 크기 는 O (n) 입 니 다. 그러면 나중에 물 어 볼 때 점 마다 고려 하 는 포인트 가 많이 줄 어 듭 니 다. 또한 dfs 에서 예비 처 리 를 할 때 부모 의 상 태 를 충분히 활용 하여 다시 한 번 합치 면 tle 입 니 다.
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 505;
const int maxm = 10005;
int f[maxm][maxn];
vector<int> G[maxm];
int n,m,q;
int from[maxm],to[maxm];
int Find(int x,int ty){
return x == f[ty][x] ? x : f[ty][x] = Find(f[ty][x],ty);
}
void dfs(int u,int fa){
for(int i = 1;i <= n;i++){
f[u][i] = f[fa][i];
}
int fx = Find(from[u],u);
int fy = Find(to[u],u);
if(fx != fy){
f[u][fx] = fy;
}
for(int i = 0;i < G[u].size();i++){
int v = G[u][i];
dfs(v,u);
}
}
int main(){
int T;
int cas = 0;
cin >> T;
while(T--){
cin >> n >> m;
for(int i = 1;i <= m;i++) G[i].clear();
for(int i = 2;i <= m;i++){
int par;
scanf("%d",&par);
G[par].push_back(i);
}
for(int i = 1;i <= n;i++) f[1][i] = i;
for(int i = 1;i <= m;i++){
scanf("%d%d",from + i,to + i);
}
dfs(1,1);
scanf("%d",&q);
printf("Case #%d:
",++cas);
for(int i = 1;i <= q;i++){
int ki;
scanf("%d",&ki);
for(int j = 1;j <= n;j++){
f[0][j] = j;
}
int num = n;
for(int j = 1;j <= ki;j++){
int a;scanf("%d",&a);
for(int k = 1;k <= n;k++){
int ty = Find(k,a);
if(ty != k){
int x = Find(ty,0);
int y = Find(k,0);
if(x != y){
num--;
f[0][x] = y;
}
}
}
}
printf("%d
",num);
}
}
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에 따라 라이센스가 부여됩니다.