CCSP 子图计数（p1）

输入输出样例

样例1

输入

4 5
SCPC
1 2
2 3
3 4
4 1
1 3

输出

4

样例2

输入

7 10
CCCSSPP
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
2 4
3 7

输出

5

题解一：枚举

将三类点分类，枚举四个点，计算这四个点相关的边组成满足题意的子图的数量。能过数据小的测试点。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
    private static boolean[][] map;
    private static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] stdin = reader.readLine().split(" ");
        final int n = Integer.parseInt(stdin[0]);
        final int m = Integer.parseInt(stdin[1]);
        List<Integer> cList = new ArrayList<Integer>(n / 2);
        List<Integer> sList = new ArrayList<Integer>(n / 4);
        List<Integer> pList = new ArrayList<Integer>(n / 4);
        String str = reader.readLine();
        for (int i = 1; i <= str.length(); ++i) {
            switch (str.charAt(i - 1)) {
            case 'C':
                cList.add(i);
                break;
            case 'S':
                sList.add(i);
                break;
            case 'P':
                pList.add(i);
                break;
            }
        }
        map = new boolean[n + 1][n + 1];
        int u, v;
        for (int i = 0; i < m; ++i) {
            stdin = reader.readLine().split(" ");
            u = Integer.parseInt(stdin[0]);
            v = Integer.parseInt(stdin[1]);
            map[u][v] = true;
            map[v][u] = true;
        }
        long start = System.currentTimeMillis();
        ans = 0;
        for (int i = 0; i < cList.size(); ++i) {
            for (int j = i + 1; j < cList.size(); ++j) {
                int p1 = cList.get(i);
                int p2 = cList.get(j);
                for (int p3 : sList) {
                    for (int p4 : pList) {
                        count(p1, p2, p3, p4);
                        count(p1, p2, p4, p3);
                        count(p1, p3, p4, p2);
                        count(p2, p3, p4, p1);
                    }
                }
            }
        }
        System.out.println(ans);
        System.out.println(System.currentTimeMillis() - start + "ms");
    }
    private static void count(int p1, int p2, int p3, int p4) {
        if (map[p1][p2] && map[p2][p3] && map[p3][p1]) {
            if (map[p1][p4]) {
                ++ans;
            }
            if (map[p2][p4]) {
                ++ans;
            }
            if (map[p3][p4]) {
                ++ans;
            }
        }
    }
}