C++14(g++5.4) 解法, 执行用时: 157ms, 内存消耗: 612K, 提交时间: 2020-06-21 12:15:17

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
const int N=10,mod=1e4+7;
typedef long long ll;
set<int>e[N];
int x,n,a,b;
ll ans=1;
void dfs(set<int> &s,int u){
 	 s.insert(u);
	 for(auto v:e[u]) 
	 	if(!s.count(v)) dfs(s,v);
}
int main(){
	scanf("%d%d",&x,&n);
	while(n--){
		scanf("%d%d",&a,&b);
		e[a].insert(b);
	}
	while(x){
		set<int>s;
		dfs(s,x%10),ans=ans*s.size()%mod,x/=10;
	}
	printf("%lld\n",ans);
} 

C++11(clang++ 3.9) 解法, 执行用时: 396ms, 内存消耗: 392K, 提交时间: 2020-06-20 20:29:01

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
set<int> G[10];
void dfs(int x,set<int> &vis)
{
	vis.insert(x);
	for(int c:G[x])
		if(vis.count(c)==0) 
			dfs(c,vis);
}
int main()
{
	int x,n;
	cin>>x>>n;
	for(int i=1;i<=n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].insert(v);
	}
    long long ans=1;
    while(x)
	{
		set<int> v;
		dfs(x%10,v);
		ans=ans*v.size()%mod;
		x/=10;
	}
	cout<<ans<<endl;
	return 0;
}