题目:Farm Irrigation
题目链接:http://210.34.193.66:8080/vj/Problem.jsp?pid=1494
题目思路:并查集
1 #include2 //并查集重点就是实现:查询某点在哪个集合、将两个集合合并 3 //查找点的祖先 4 int a[10000]; 5 int fun(int x) 6 { 7 int p=x; 8 // 初始化数组 a[i]=i; 9 // 也就是说当 a[i]==i 时,这是一个祖先,或者他是别人的子树 10 while(a[p]!=p) 11 { 12 p=a[p]; 13 } 14 // p就是祖先,下面是路径压缩 15 int q=x; 16 while(a[q]!=p) 17 { 18 x=a[q]; 19 a[q]=p; 20 q=x; 21 } 22 return p; 23 } 24 //合并两个集合 25 void join(int x,int y) 26 { 27 int xt=fun(x); 28 int yt=fun(y); 29 if(xt!=yt) 30 { 31 a[xt]=yt; 32 } 33 } 34 int n,m; 35 int bian(int i,int j) 36 { 37 return i*m+j; 38 } 39 int islian_heng(char c1,char c2) 40 { 41 if(c1=='B') 42 { 43 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 44 else return 0; 45 } 46 else if(c1=='D') 47 { 48 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 49 else return 0; 50 } 51 else if(c1=='F') 52 { 53 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 54 else return 0; 55 } 56 else if(c1=='G') 57 { 58 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 59 else return 0; 60 } 61 else if(c1=='I') 62 { 63 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 64 else return 0; 65 } 66 else if(c1=='J') 67 { 68 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 69 else return 0; 70 } 71 else if(c1=='K') 72 { 73 if(c2=='A'||c2=='C'||c2=='F'||c2=='G'||c2=='H'||c2=='I'||c2=='K') return 1; 74 else return 0; 75 } 76 else return 0; 77 } 78 int islian_shu(char c1,char c2) 79 { 80 if(c1=='C') 81 { 82 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1; 83 else return 0; 84 } 85 else if(c1=='D') 86 { 87 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1; 88 else return 0; 89 } 90 else if(c1=='E') 91 { 92 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1; 93 else return 0; 94 } 95 else if(c1=='H') 96 { 97 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1; 98 else return 0; 99 }100 else if(c1=='I')101 {102 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1;103 else return 0;104 }105 else if(c1=='J')106 {107 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1;108 else return 0;109 }110 else if(c1=='K')111 {112 if(c2=='A'||c2=='B'||c2=='E'||c2=='G'||c2=='H'||c2=='J'||c2=='K') return 1;113 else return 0;114 }115 else return 0;116 }117 int main()118 {119 char s[100][100];120 while(scanf("%d%d",&n,&m)!=EOF)121 {122 if(n==-1&&m==-1) break;123 for(int i=0;i