# hihoCoder 1087 & week 63-1-Hamiltonian Cycle

hihoCoder 1087 & week 63-1-Hamiltonian Cycle
#1087 : Hamiltonian Cycle

Given a directed graph containing n vertice (numbered from 1 to n) and m edges. Can you tell us how many different Hamiltonian Cycles are there in this graph?
A Hamiltonian Cycle is a cycle that starts from some vertex, visits each vertex (except for the start vertex) exactly once, and finally ends at the start vertex.
Two Hamiltonian Cycles C1, C2 are different if and only if there exists some vertex i that, the next vertex of vertex i in C1 is different from the next vertex of vertex i in C2.

The first line contains two integers n and m. 2 <= n <= 12, 1 <= m <= 200.
Then follows m line. Each line contains two different integers a and b, indicating there is an directed edge from vertex a to vertex b.

Output an integer in a single line -- the number of different Hamiltonian Cycles in this graph.

 样例输入 样例输出 3 3 1 2 2 1 1 3 0

4 7
1 2
2 3
3 4
4 1
1 3
4 2
2 1

2

```DFS(int nowVertex, bool visitedVertex, int path, int length)
visitedVertex[ nowVertex ] = True;
If (all Vertex is visited) Then
Count = Count + 1
Else
For (u is next vertex of nowVertex)
If (not visitedVertex[ u ]) Then
path[ length ] = u
DFS(u, visitedVertex, path, length + 1)
End If
End For
End If
visitedVertex[ nowVertex ] = False
```

```const int MAXN = 14;
int edge[ MAXN ];//edge[i]二进制中1的序号表示i能访问的节点编号
int p[1 << MAXN];//p[1<<i]=i+1表示只有i点访问了的情况为1<<i
int cnt;
void dfs(int nowVertex, int unused) {
if (!unused) {//所有节点访问完了
cnt += (edge[nowVertex] & 1);//判断能否回到起始节点1
return ;
}
int rest = unused & edge[ nowVertex ];//剩余的能访问到的未访问节点
while (rest) {
int tp = rest & (-rest);//依次取出可访问节点
dfs(p[ tp ], unused - tp);//访问
rest -= tp;
}
return ;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i)
p[ 1 << i ] = i + 1;
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
edge[u] |= 1 << (v - 1);//记录u能访问节点的情况
}
dfs(1, (1 << n) - 2);//初始的时候访问了1号节点，所以-1-1=-2
printf("%d\n", cnt);
return 0;
}
```

```For numberOfOnes = n-1 .. 0
For (unused | the number of ones of unused equals numberOfOnes)
For nowVertex = 1 .. n
For prevVertex = 1 .. n
If (unused & (1 << (nowVertex - 1)) == 0) and (prevVertex != nowVertex) and (edge[ prevVertex ] & (1 << (nowVertex - 1)) != 0) Then
f[ nowVertex ][ unused ] = f[ nowVertex ][ unused ] + f[ prevVertex ][unused + (1 << (nowVertex - 1))]
End If
End For
End For
End For
End For
```

```#include<iostream>
#include<cstdio>
#include<vector>
#include<iterator>
using namespace std;
const int MAXN = 14;
int edge[MAXN];
int p[1 << MAXN];
int f[MAXN][1<<MAXN];
//n位二进制中出现k个1的所有排列情况
vector<int> dfs(int n, int k)
{
if (k == 0)//出现0个1，只有一种情况，全0
return vector<int>(1, 0);
else
{
//**********  n==k的情况  **************************
vector<int> r = dfs(n - 1, k - 1);//n-1位中出现k-1个1//将大问题分解成小问题
for (int &i : r)
{
i |= (1 << (n - 1));//补上第n位也为1
}
//**************************************************
if (n > k)
{
vector<int> t = dfs(n - 1, k);//此时第n位可以为0
copy(t.begin(), t.end(), back_inserter(r));
}
return r;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i)
p[1 << i] = i + 1;
while (m--)
{
int u, v;
scanf("%d %d", &u, &v);
edge[u] |= 1 << (v - 1);
}
f[1][(1 << n) - 2] = 1;
for (int numberOfOnes = n - 1; numberOfOnes >= 0; numberOfOnes--)
{
vector<int> stat = dfs(n, numberOfOnes);
for (int i = 0; i < stat.size(); i++)
{
int s = stat[i];
for (int nowVertex = 1; nowVertex <= n; nowVertex++)
{
for (int prevVertex = 1; prevVertex <= n; prevVertex++)
{
if ((s & (1 << (nowVertex - 1))) == 0 && prevVertex != nowVertex && (edge[prevVertex] & (1 << (nowVertex - 1))) != 0)
f[nowVertex][s] += f[prevVertex][s | (1 << (nowVertex - 1))];
}
}
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (edge[i] & 1)
cnt += f[i][0];
printf("%d\n", cnt);
return 0;
}
```