A1. 道路修建 Small
Time Limit: 1000ms
Memory Limit: 131072KB
64-bit integer IO format: %lld Java class name: Main无向图
初始有
个点，从
到依次标号，但是没有边，
接下来有
次操作，从到依次标号，你需要对每种操作输出相应的结果，操作分为两种：
输入格式 | 操作说明 | 输出结果 |
0_u_v | 加入一条连接标号为 | 输出加边后图 |
1_u_v | 查询标号为 | 如果连通，输出 |
，表示最早在第
。（输入格式中的下划线‘_’表示实际输入文件中的空格）
Input
第一行是一个正整数
，表示测试数据的组数，
对于每组测试数据，
第一行包含两个整数
、
，
接下来行，每行是
个整数
、
、
，请注意所给的、均是经过加密的，
解密方式是
、
，其中
表示上一次操作的输出结果，
初始
，保证
，解密后
且
。
Output
对于每组测试数据，
输出行，每行包含一个整数，表示操作的输出结果。
Sample Input
1 4 7 0 1 2 1 1 0 0 1 3 0 0 1 1 0 1 0 1 7 1 0 5
Sample Output
3 0 2 2 3 1 6
思路：并查级。
用并查集判断有几个联通块。然后每次加点的时候将不同的两个集合合并到一起时，每个集合里的点相连通的时间最早时间就是此时合并的时间，开个yy数组记录就行了。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<string.h>
4 #include<stdlib.h>
5 #include<math.h>
6 #include<iostream>
7 #include<vector>
8 #include<cstdio>
9 #define sc(x) scanf("%I64d",&x)
10 #define pr(x) printf("%I64d",x)
11 #define prr(x) printf(" %I64d",x)
12 #define prrr(x) printf("%I64d ",x)
13 typedef long long ll;
14 const ll N=1e9+7;
15 using namespace std ;
16 vector<int>aa[1005];//记录集合中的点
17 int bb[10005];
18 int dd[10005];
19 int cc[10005];//并差集权重数组
20 int gg[10005];
21 int yy[1005][1005];//记录最早联通的时间
22 int main(void)
23 {
24 int i,j,k,p,q,n,m,s;
25 scanf("%d",&k);
26 while(k--)
27 {
28 for(i=0; i<1005; i++)
29 {
30 aa[i].clear();
31 aa[i].push_back(i);//先将自己加入集合
32 bb[i]=i;
33 cc[i]=1;
34 }
35 scanf("%d %d",&n,&m);
36 memset(yy,0,sizeof(yy));
37 int nn=0;//初始化输出
38 int ans=0;
39 for(i=1; i<=m; i++)
40 {
41 scanf("%d %d %d",&s,&p,&q);
42 p=p^nn;
43 q=q^nn;
44 if(s==0)
45 {
46 int x,y;
47 for(x=p; bb[x]!=x;)
48 {
49 x=bb[x];
50 }
51 for(y=q; bb[y]!=y;)
52 {
53 y=bb[y];
54 }
55 if(x!=y)
56 {
57 yy[p][q]=i;
58 yy[q][p]=i;
59
60 for(j=0; j<aa[x].size(); j++)
61 {
62 for(int r=0; r<aa[y].size(); r++)
63 {
64 yy[aa[x][j]][aa[y][r]]=yy[aa[y][r]][aa[x][j]]=i;
65
66 }
67 }//记录联通最早的时间，因为他们在此时刚和并
68 yy[x][y]=i;
69 yy[y][x]=i;
70 if(cc[x]>cc[y])//合并集合
71 {
72 cc[x]+=cc[y];
73 bb[y]=x;
74 for(j=0; j<aa[y].size(); j++)
75 {
76 aa[x].push_back(aa[y][j]);
77 }
78 aa[x].push_back(y);
79 aa[y].clear();
80
81 }
82 else
83 {
84 cc[y]+=cc[x];
85 bb[x]=y;
86 for(j=0; j<aa[x].size(); j++)
87 {
88 aa[y].push_back(aa[x][j]);
89 }
90 aa[y].push_back(x);
91 aa[x].clear();
92
93 }
94 }
95 int gh;
96 for(int w=1; w<=n; w++)
97 {
98 for( gh=w; bb[gh]!=gh;)
99 {
100 gh=bb[gh];
101 }
102 gg[w]=gh;
103 }
104 sort(gg+1,gg+1+n);//判断联通段
105 int cnt=1;
106 for(int h=2; h<=n; h++)
107 {
108 if(gg[h]!=gg[h-1])
109 {
110 cnt++;
111 }
112 }
113
114 nn=cnt;
115 printf("%d ",cnt);
116 }
117 else if(s==1)
118 {
119 printf("%d ",yy[p][q]);
120 nn=yy[p][q];
121 }
122 }
123
124 }
125 return 0;
126 }