Java(javac 1.8) 解法, 执行用时: 1532ms, 内存消耗: 11272K, 提交时间: 2020-05-18 19:53:01

import java.util.*;
public class Main
{
    static int cur1 = 0;
    static int[] a = new int[10000];
    static int[][] str = new int[20][20];
    public static void main(String[] args)
    {   
        Scanner sc = new Scanner(System.in);
        String[] str1 = sc.nextLine().split(" ");
        int num1 = Integer.parseInt(str1[0]);
        int num2 = Integer.parseInt(str1[1]);
        for(int i = 0;i < num2;i++)
        {
            String[] str2 = sc.nextLine().split(" ");
            int x = Integer.parseInt(str2[1]);
            int y = Integer.parseInt(str2[2]);
            if(str2[0].equals("S"))
            {
            str[x][y] = 1;
            str[y][x] = 1;
            }else{
                str[y][x] = -1;
                str[x][y] = -1;
            }
        }
        start_process(1,num1);
        System.out.println(cur1);
    }
    public static void start_process(int tmp,int num1)
    {
        if(tmp > num1)
        {
            cur1++;
            return;
        }
        for(int i = 1;i <=3;i++)
        {
            int cur2 = 0;
            for(int j = 0;j < tmp;j++)
            {
                if(i != a[j]&&str[tmp][j] == 1)
                {
                    cur2 = 1;
                    break;
                }
                if(i == a[j]&&str[tmp][j] == -1)
                {
                   cur2 = 1;
                   break;
                }
            }
            if(cur2 == 0)
            {
               a[tmp] = i;
               start_process(tmp+1,num1);
               a[tmp] = 0;
            }
}
    }
}

C++14(g++5.4) 解法, 执行用时: 538ms, 内存消耗: 500K, 提交时间: 2020-05-22 13:32:58

#include<bits/stdc++.h>
using namespace std;
const int MX=100;
char s[MX];
int ans=0,n,k,val[MX],dis[MX][MX];

void dfs(int u){
    if( u==n+1 ){
        ans++;
        return ;
    }
    for( int i=1 ; i<=3 ; i++ ){
        int flag=1;
        for( int v=1 ; v<u ; v++ ){
            if( dis[u][v]==1 && val[v]!=i ){
                flag=0;
                break;
            }
            if( dis[u][v]==-1 && val[v]==i ){
                flag=0;
                break;
            }
        }
        if( flag ){
            val[u]=i;
            dfs(u+1);
            val[u]=0;
        }
    }
}


int main()
{
//    freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&k);
    for( int i=1,u,v ; i<=k ; i++ ){
        scanf("%s %d %d",s,&u,&v);
        if( s[0]=='S' )
            dis[u][v]=dis[v][u]=1;
        else
            dis[u][v]=dis[v][u]=-1;
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 820ms, 内存消耗: 604K, 提交时间: 2020-05-18 21:36:36

#pragma GCC optimize(3)
#include <cstdio>
using namespace std;
int g[20][20];
int n,k,ans=0,a[100005];
char op[2];
void dfs(int now)
{
	if(now>n){ans++;return;}
	for(int i=1;i<=3;i++)
	{
		bool v=true;
		for(int j=1;j<now;j++)
		{
			if(i!=a[j]&&g[now][j]==1){v=false;break;}
			if(i==a[j]&&g[now][j]==-1){v=false;break;}
		}
		if(v)a[now]=i,dfs(now+1),a[now]=0;
	 }
}
int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1,x,y;i<=k;i++)
	{
		scanf("%s %d %d",op,&x,&y);
		if(op[0]=='S')g[x][y]=g[y][x]=1;
		else g[x][y]=g[y][x]=-1;
	}	
	dfs(1);printf("%d",ans);
}