给定一个完全图和一些必须包含在哈密顿路中的边。。求这样的哈密顿路有几条。。
很显然如果一个点连接了3条或以上的必须边的话。。就无解了。。所以必须边一定是成链出现的。。
一个有2个或以上节点组成的必须链有一个方向，就是因子2
同时如果有n条链的话（单个节点也算链。。）。。那么排列也有n！的因子。。
全部乘起来就OK了。。
Code:
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int mod=1000000007;
class HamiltonPath
{
bool vis[50];
vector<string> map;
int num;
void dfs(int x)
{
vis[x]=true;num++;
for(int i=0;i<map.size();i++)
if(map[x][i]==’Y’&&!vis[i]) dfs(i);
}
public:
int countPaths(vector <string> m)
{
vector<int> d(m.size(),0);int cnt=0;map=m;long long ans=1;
for(int i=0;i<m.size();i++)
for(int j=0;j<m.size();j++)
{
if(m[i][j]==’Y’) d[i]++;
if(d[i]>2) return 0;
}
memset(vis,0,sizeof(vis));
for(int i=0;i<m.size();i++)if(!vis[i]){num=0;dfs(i);cnt++;if(num>1)ans*=2,ans%=mod;}
for(int i=1;i<=cnt;i++)ans*=i,ans%=mod;
return ans;
}
};