Problem Statement
|
| |
There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.
John plans to travel through the country using the following rules:
- He must start in one city and end in another city after travelling exactly N-1 roads.
- He must visit each city exactly once.
- You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.
Return the number of paths he can choose, modulo 1,000,000,007. |
Definition
|
| |
| Class: |
HamiltonPath |
| Method: |
countPaths |
| Parameters: |
String[] |
| Returns: |
int |
| Method signature: |
int countPaths(String[] roads) |
| (be sure your method is public) |
|
| |
|
Constraints
|
| - |
roads will contain between 2 and 50 elements, inclusive. |
| - |
Each element of roads will contain n characters, where n is the number of elements in roads. |
| - |
Each character in roads will be 'Y' or 'N'. |
| - |
The i-th character in the i-th element of roads will be 'N'. |
| - |
The j-th character in the i-th element of roads and the i-th character in the j-th element of roads will be equal. |
Examples
|
| 0) |
|
| |
|
|
Returns: 4
|
| The example from the problem statement. |
|
|
| 1) |
|
| |
{"NYYY",
"YNNN",
"YNNN",
"YNNN"}
|
|
Returns: 0
|
| It's impossible to travel all these roads while obeying the other rules. |
|
|
| 2) |
|
| |
|
| 3) |
|
| |
{"NNNNNY",
"NNNNYN",
"NNNNYN",
"NNNNNN",
"NYYNNN",
"YNNNNN"}
|
|
Returns: 24
|
|
|
|
求哈密頓通路的數目，題目中指定了一些道路必須經過。
1。做法是求連通分支，縮點，并判斷有沒有出現環或者非正常情況，若出現直接返回0。
2。求連通分支數的全排列；
3。遍歷所有連通分支
4。如果該連通分支擁有的點數>=2,則結果乘以2，即可得到答案.
求的時候要注意mod操作，要用long long 保存中間數據，(a*b)mod c中 a*b可能溢出32位整數。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
int graph[51][51];
int n;
int v[51];
int ID[51];
int num[51];
int gcc=0;
int flag=0;
void dfs(int f,int k)
{
if(flag==1)
return;
ID[k]=gcc;
num[gcc]++;
int i;
for(i=1;i<=n;i++)
{
if(graph[k][i]&&(v[i]==1)&&(i!=f))
{
flag=1;
return;
}
if(graph[k][i]&&(v[i]==0))
{
v[i]=1;
dfs(k,i);
}
}
}
class HamiltonPath
{
int i,j;
public:
int countPaths(vector <string> roads)
{
n=roads[0].length();
for(i=0;i<n;i++)
{
for(j=0;j<=n;j++)
{
if(roads[i][j]=='Y')
graph[i+1][j+1]=1;
}
}
for(i=1;i<=n;i++)
{
if(!v[i])
{
v[i]=1;
gcc++;
dfs(-1,i);
}
}
if(flag==1)
return 0;
int cnt=0;
for(i=1;i<=n;i++)
{
cnt=0;
for(j=1;j<=n;j++)
{
if(graph[i][j]==1)
cnt++;
}
if(cnt>2)
return 0;
}
long long res=1;
for(i=1;i<=gcc;i++)
{
res*=i;
res%=1000000007;
if(num[i]>=2)
{
res*=2;
res%=1000000007;
}
}
return res;
}
};
第一次寫tc,寫的不好還請大家多多指點 :-)