HDU 5923 및 검색 집합

전송 문: 제목
제목:
제목 은 이해 하기 어렵 습 니 다. 읽 은 후에 바로 하나의 집합 을 찾 습 니 다. 다른 블 로 그 는 지속 적 으로 사용 할 수 있 고 집합 을 찾 을 수 있 습 니 다. 저 는 보통 집합 을 사용 하고 AC 도 사용 할 수 있 습 니 다. 지속 적 이 고 집합 을 찾 을 수 없 기 때 문 입 니 다.그림 이 하나 있 고 나무 가 한 그루 있 습 니 다. 그리고 나무 에 있 는 모든 결점 은 그림 속 의 가장자리 에 있 는 정보 입 니 다. 그래서 그림 에 m 개의 가장자리 가 있 으 면 나무 에 m 개의 정점 이 있 습 니 다.그리고 q 번 의 질문 이 있 습 니 다. 매번 질문 할 때마다 몇 가지 점 을 주 고 나무 에서 이 점 을 찾 습 니 다. 그리고 그들의 모든 조상 들 도 이 집합 에 가입 한 다음 에 이 집합 을 그림 에 투사 하여 그림 의 연결 분량 을 구 합 니 다.정 답 은 분량 을 연결 하 는 개수 다.
문제 풀이:
4. 567917. 뿌리 결점 은 반드시 모든 조상 들 의 일원 이라는 것 을 발견 하기 어렵 지 않다. 우 리 는 DFS 를 한 번 만 한 다음 에 경 로 를 옮 겨 다 니 면 문의 의 집합 이다. 그리고 우 리 는 어떻게 연결 분량 을 구 하 는 지 고려 해 야 한다
4. 567917. 우 리 는 연결 분량 의 개 수 를 사용 하고 조사 할 수 있다. 왜냐하면 뿌리 노드 가 같 기 때문에 똑 같은 연결 분량 에 있 을 것 이다
4. 567917. 우 리 는 DFS 에서 하위 노드 에 부모 노드 의 계승 과 집합 을 찾 을 수 있 습 니 다. 그러면 Query 를 할 때 우 리 는 모든 노드 의 집합 을 고려 하고 조사 하면 됩 니 다. 그 다음 에 두 개의 for 순환, 첫 번 째 for 는 모든 query 를 스 캔 하고 두 번 째 for 스 캔 그림 의 모든 결점 을 스 캔 한 다음 에 다시 한 번 집합 을 찾 고 마지막 으로 하나의 for 로 한 번 스 캔 하면 됩 니 다.몇 개의 노드 만 있 으 면 몇 개의 연결 분량 이 있다

#include 
#include 
#include 
#include 
#include 
#define debug(x) cout<
#define INF 0x3f3f3f3f
using namespace std;

const int maxv = 510;//     
const int maxe = 10010;//    

int n, m, t1, t2;
int head[maxe], cnt; //      ,   head       ，           ，        ，  MLE
int root[maxe][maxv];//       
bool vis[maxv]; int Query, query[maxe], qcnt, ans; //      
struct Edge {
    int to, next;
} edge[maxe];
pair<int, int> pii;
vectorint, int> > vpii;

void init() {
    memset(head, -1, sizeof head);
    vpii.clear();
    cnt = 0;
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++)
            root[i][j] = j;//                ，   
}
void init_Query() {
    memset(vis, false, sizeof vis);
    ans = 0;
}
void addedge(int from, int to) {
    edge[cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt++;
}
int Find(int tree_point, int graph_point) {//   
    if (root[tree_point][graph_point] == graph_point)
        return graph_point;
    return root[tree_point][graph_point] = Find(tree_point, root[tree_point][graph_point]);
}
void mix(int tree_point, int graph_point1, int graph_point2) {//   
    graph_point1 = Find(tree_point, graph_point1);
    graph_point2 = Find(tree_point, graph_point2);
    if (graph_point1 != graph_point2)
        root[tree_point][graph_point2] = graph_point1;
}
void dfs(int u) {
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        memcpy(root[v], root[u], sizeof root[v]);
        mix(v, vpii[v - 1].first, vpii[v - 1].second);
        dfs(v);
    }
}
int main(void) {
    int T, kase = 1;
    scanf("%d", &T);
    while (T--) {
        printf("Case #%d:
", kase++);
        scanf("%d%d", &n, &m);
        init();
        addedge(0, 1);
        for (int i = 2; i <= m; i++)
            scanf("%d", &t1), addedge(t1, i); //  
        for (int i = 0; i < m; i++) //  
            scanf("%d%d", &t1, &t2), pii = make_pair(t1, t2), vpii.push_back(pii);
        dfs(0);
        scanf("%d", &Query);
        while (Query--) {
            init_Query();
            scanf("%d", &qcnt);
            for (int i = 0; i < qcnt; i++)
                scanf("%d", &query[i]);

            memcpy(root[m + 1], root[query[0]], sizeof root[m + 1]);//   Query   ，              ，             
            for (int i = 1; i < qcnt; i++)//     query
                for (int j = 1; j <= n; j++)//        
                    mix(m + 1, Find(query[i], j), j);//       
            for (int i = 1; i <= n; i++)
                if (!vis[Find(m + 1, i)])
                    vis[Find(m + 1, i)] = true, ans++;

            cout << ans << endl;
        }
    }
    return 0;
}