ACM Arabella Collegiate Programming Contest 2015 F. Palindrome 并查集

本文主要是介绍ACM Arabella Collegiate Programming Contest 2015 F. Palindrome 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/gym/100676/attachments

题意：

给一个字符串，有一些约束条件，两个位置要相同，有一些是问号，求最后有多少种方案回文？

分析：

每一个节点是一个集合，要是不同，有一个是问号，那么这个问号就是确定的（约束条件中，和回文的对称位置），单独的集合，他又是问号，就可以放26个字母了；

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int MAXN = 50005;
 8 
 9 char s[MAXN];
10 int n,m;
11 int f[MAXN],flag;
12 
13 int Find(int x)
14 {
15     if(x == f[x])
16         return x;
17     else return f[x] = Find(f[x]);
18 }
19 
20 void judge(int x,int y)
21 {
22     if(s[x] == s[y])
23         f[x] = y;
24     else if(s[x] == '?')
25         f[x] = y;
26     else if(s[y] == '?')
27         f[y] = x;
28     else flag = true;
29 }
30 
31 int main()
32 {
33     //freopen("in.txt","r",stdin);
34     int ncase;
35     scanf("%d",&ncase);
36     while(ncase--) {
37         flag = false;
38         scanf("%d%d%s",&n,&m,s);
39         for(int i = 0;i < n; i++)
40             f[i] = i;
41         for(int i = 0,j = n-1;i < j; i++,j--) {
42             judge(i,j);
43         }
44         for(int i = 0;i < m; i++) {
45             int a,b;
46             scanf("%d%d",&a,&b);
47             a--,b--;
48             judge(Find(a),Find(b));
49         }
50         if(flag) {
51             printf("0\n");
52             continue;
53         }
54         else {
55             long long ans = 1;
56             for(int i = 0;i < n; i++) {
57                 if(f[i] == i && s[i] == '?') {
58                     ans *= 26;
59                     ans %= 1000000007;
60                 }
61             }
62             printf("%lld\n",ans);
63         }
64     }
65     return 0;
66 }