[原创]HDU 5923 Prediction [可持久化并查集]【数据结构】

2017-01-21 16:26:30 Tabris_ 阅读数：934

博客爬取于2020-06-14 22:42:03
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54646369

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5923
-------------------------------------------------------------------------------.
Prediction

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 693 Accepted Submission(s): 167

Problem Description
There is a graph G=⟨VG,EG⟩ with |VG|=n and |EG|=m, and a magic tree T=⟨VT,ET⟩) rooted at 1, which contains m vertices.

Each vertex of the magic tree corresponds to an edge in the original graph G and each edge occurs in the magic tree exactly once.

Each query includes a set S(S⊆VT), and you should tell Mr. Frog the number of components in the modified graph G‘=(VG,E‘G), where E‘G is a set of edges in which every edge corresponds to a vertex v in magic tree T satisfying at least one of the following two conditions：

∙v∈S.
∙v is an ancestor of some vertices in S.

Note that the queries are independent, and namely one query will not influence another.

Input
The input contains several test cases and the first line of the input data is an integer T, denoting the number of test cases.

For each test case, the first line contains two integers n and m(1≤n≤500,1≤m≤10000), where n is the number of vertices and m is the number of edges.

The second line contains m - 1 integers describing the magic tree, i-th integer represents the parent of the (i + 1)-th vertex.

Then the following m lines describe the edges of the graph G. Each line contains two integers u and v indicating the two ends of the edge.

The next line contains only one integer q(1≤q≤50000), indicating the number of queries.

Then the following q lines represent queries, i-th line represents the i-th query, which contains an integer ki followed by ki integers representing the set Si.

It is guarenteed that∑i=1qki≤300000.∑_{i=1}^{q}{ki}≤300000.

Output
For each case, print a line “Case #x:”, where x is the case number (starting from 1).

For each query, output a single line containing only one integer representing the answer, namely the number of components.

Sample Input
1
5 4
1 1 3
1 2
2 3
3 4
4 5
3
1 2
2 2 3
2 2 4

Sample Output
Case #1:
3
2
1

Hint

magic tree and the original graph in the sample are:

1
2
3
4
5
In the first query, S = {2} and the modified graph G' = {{1, 2, 3, 4}, {(1, 2), (2, 3)} }, thus the number of the components in the modified graph is 3.
In the second query, S = {1, 2, 3}, where 1 is the ancestor of 2 (and 3) in the magic tree, and the modified graph G'' = {{1, 2, 3,4}, {(1, 2), (2, 3), (3, 4)} },
 therefore the number of the components in the modified graph is 2.
In the third query, S = {1, 2, 3, 4}, where 1 is the ancestor of 2 (and 4), 3 is the ancestor of 4, and the modified graph G' = {{1, 2, 3,4}, {(1, 2), (2, 3), (3,4), (4, 5)} },
therefore the answer equals to 1.

-------------------------------------------------------------------------------.

题目大意：
就是有一个n个节点，m条边的图和一个m-1个节点的树（根结点是1）。
树的每个节点对应图的一个边，
每次在树中选中一些节点的集合，就将图中对应集合中所有元素与所有的父节点的边连接起来，问你现在图中有多少个联通块。

解题思路：
对于每一个节点的父节点我们都可以用并查集来处理，这样就能知道在选边的时候都选哪些边了，但是对于直接处理之后我们不能很好的将父节点和子节点相区分开，所以对于每个点的情况，分别做一个并查集，这样的话就能区分父节点和子节点了。

之后在对图进行并查集的操作，来统计有几个联通块就行了。

在处理并查集的时候，对于子节点来说，是满度父节点的集合关系的，所以只要把之前的并查集规则复制一遍，在新处理一下当前节点的就行了。处理过程就是dfs一次树，同时处理并查集 复杂度是O(N∗M)O(N*M)

这种算是访问历史版本的并查集应该也算是可持久化并查集了

在每次查询的时候,我们对每个点均处理依次,也只是将跟节点的在一个集合的点放到一个集合.复杂度是O(∑i=1qki∗N)O(∑_{i=1}^{q}{ki}*N)

总复杂度就是O(N∗M+∑i=1qki∗N)O(N*M+∑_{i=1}^{q}{ki}*N)

附本题代码
-------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 100000+7;
const int    MOD = 1e9+7;
const double eps = 1e-6;
const double PI  = acos(-1.0);
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}


/***********************************************************************/
vector<int >T[10005];//树
//vector<pair<int ,int > >G;
int G[10005][2];//图
int pre[10005][505];//并查集
int vis[505];//结果
int n,m;

int findi(int x,int y){
    int r=x;
    while(pre[y][r]!=r) r=pre[y][r];
    int i=x,j;
    while(i!=j){
        j=pre[y][i];
        pre[y][i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y,int xy){
    int fx=findi(x,xy),fy=findi(y,xy);
    if(fx!=fy) pre[xy][fx]=fy;
}

void dfs(int x,int fa){
    for(int i=1;i<=n;i++) pre[x][i]=pre[fa][i];
    join(G[x][0],G[x][1],x);
    int len = T[x].size();
    for(int i=0;i<len;i++) dfs(T[x][i],x);
}

int main(){
    int _ = 1,kcase;
    while(~scanf("%d",&_)){
        kcase = 0;
        while(_--){

            int x,u,v;
            scanf("%d%d",&n,&m);
            for(int i=0;i<=n;i++)pre[0][i]=i;
            for(int i=1;i<=m;i++)T[i].clear();
            for(int i=2;i<=m;i++){
                scanf("%d",&x);
                T[x].pb(i);
            }

            for(int i=1;i<=m;i++){
                scanf("%d%d",&u,&v);
                G[i][0]=u,G[i][1]=v;
                //G.pb(mp(v,u));
            }

            dfs(1,0);

            //puts("------");

            printf("Case #%d:\n",++kcase);
            int q,k;
            scanf("%d",&q);
            while(q--){
                for(int i=0;i<=n;i++) pre[0][i]=i,vis[i]=0;
                scanf("%d",&k);
                for(int i=0;i<k;i++){
                    scanf("%d",&x);
                    for(int j=1;j<=n;j++){
                        int ty=findi(j,x);
                        if(ty!=j) join(j,ty,0);
                    }
                }

                int ans=0;
                for(int i=1;i<=n;i++){  //计算联通块
                    int tem=findi(i,0);
                    if(!vis[tem]) ans++;
                    vis[tem]=1;
                }
                printf("%d\n",ans);
            }

        }
    }
    return 0;
}