HDU5923——Prediction（資料結構，并查集）

Prediction

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 476    Accepted Submission(s): 109

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  ∑qi=1ki≤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:


    
        
  
               


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.
   
        

題意：分别給你一個有根樹還有一個圖，有根樹得每個節點代表圖的一條邊。每次詢問給你一個集合，把集合裡所有的點以及所有點的祖先節點代表得邊連起來。問連接配接後的圖中有多少個連通分量

思路：很容易發現，用DFS周遊一棵樹的時候。是從祖先周遊到兒子的。那麼可以建立m個并查集，在周遊的時候預處理出每一個節點及其祖先節點的并查集。然後查詢的時候隻需要把這些并查集合并即可。

#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <ctime>
#include <cstdlib>
#include <iostream>
#define pi 3.1415926
#define mod 1000000007
#define MAXM 10010
#define MAXN 510
#define INF 0x3f3f3f3f3f3f3fLL
using namespace std;

struct edge{
	int v,next;
}e[MAXM];
int head[MAXM];
int tot=0;

void add(int u,int v){
	e[tot].v=v;
	e[tot].next=head[u];
	head[u]=tot++;
}

struct node{
	int u,v;
};

std::vector<node> G;

int f[MAXM][MAXN];
void init(int m,int n){
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=j;
		}
	}
}
int find(int m,int x){
	if(f[m][x]==x)
		return x;
	else
		return f[m][x]=find(m,f[m][x]);
}
void unite(int m,int x,int y){
	x=find(m,x);
	y=find(m,y);
	if(x==y)
		return;
	else
		f[m][y]=x;
}

void dfs(int x){
  	for(int k=head[x];k!=-1;k=e[k].next){
 		int v=e[k].v;
		memcpy(f[v],f[x],sizeof(f[v]));
		unite(v,G[v-1].u,G[v-1].v);
		//if(x!=0)
          //  unite(v,G[x-1].u,G[v-1].u);
		dfs(v);
	}
}

int res[MAXM];
int vis[MAXN];
int main()
{
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++){
		printf("Case #%d:\n",cas);
		int n,m;
		scanf("%d%d",&n,&m);
		init(m,n);
		tot=0;
		G.clear();
		memset(head,-1,sizeof(head));
		add(0,1);
		for(int i=2;i<=m;i++){
			int x;
			scanf("%d",&x);
			add(x,i);
		}
		for(int i=0;i<m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			node temp;
			temp.u=u,temp.v=v;
			G.push_back(temp);
		}
		dfs(0);
		int q;
		scanf("%d",&q);
		while(q--){
			int cnt;
			memset(vis,0,sizeof(vis));
			scanf("%d",&cnt);
			for(int i=0;i<=n;i++){
				f[m+1][i]=i;
			}
			for(int i=0;i<cnt;i++){
				scanf("%d",&res[i]);
			}
			memcpy(f[m+1],f[res[0]],sizeof(f[m+1]));
			for(int i=1;i<cnt;i++){
                for(int j=1;j<=n;j++){
				int r=find(res[i],j);
				unite(m+1,r,j);
				}
				//unite(m+1,G[res[0]-1].u,G[res[i]-1].u);
			}
			int ans=0;
			for(int i=1;i<=n;i++){
 				int temp=find(m+1,i);
				//cout<<temp<<endl;
				if(!vis[temp]){
                    	vis[temp]=1;
				ans++;
				}
			}
			printf("%d\n",ans);
		}
	}
}