hdu 5923 (집합 유지보수 블록)

5746 단어 데이터 구조
앞의 박문 에서 이 문 제 는 t 라 고 말 했 는데 오늘 다른 사람의 작법 을 보 니 복잡 도가 확실히 상수 가 좀 크다 는 것 을 발견 했다.
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; }

좋은 웹페이지 즐겨찾기