# The Fourth Dimension Space

## Topcoder SRM 452 ,DIV 2 1000 HamiltonPath

### 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)

 ```                                    {"NYN", "YNN", "NNN"}```
`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)

 ```                                    {"NYY", "YNY", "YYN"}```
`Returns: 0`
 This is also impossible.
3)

 ```                                    {"NNNNNY", "NNNNYN", "NNNNYN", "NNNNNN", "NYYNNN", "YNNNNN"}```
`Returns: 24`

1。做法是求连通分支，缩点，并判断有没有出现环或者非正常情况，若出现直接返回0。
2。求连通分支数的全排列；
3。遍历所有连通分支
4。如果该连通分支拥有的点数>=2,则结果乘以2，即可得到答案.

#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:

{
n

for(i=0;i<n;i++)

{

for(j=0;j<=n;j++)

{

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;
}

}
;

posted on 2009-11-06 14:35 abilitytao 阅读(1235) 评论(1)  编辑 收藏 引用

good...