题目描述
农夫约翰在周末进行高能物理实验的时候发生了一些意外,导致他的农场上出现了 N 个虫洞(N 是偶数)。
我们将农场视作一个二维平面,每个虫洞都位于其中的不同点上,也就是说所有虫洞的坐标 (x,y) 均不相同。
根据他的计算,这些虫洞将形成 N/2 个连接对。
例如,如果虫洞 A 和 B 成对连接,那么进入虫洞 A 的生物会从虫洞 B 出来,反之亦然。
这将引发很不愉快的后果。
假设虫洞 A(1,1) 和虫洞 B(3,1) 成对连接,奶牛贝茜从 (2,1) 位置开始沿 x 轴正向移动。
贝茜就会进入到虫洞 B 中,并从虫洞 A 处出来,然后再次移动到虫洞 B 中,以此类推,陷入无限循环。
约翰知道每个虫洞的具体坐标位置,同时知道贝茜会一直沿着 x 轴正向移动,但是她当前的位置约翰并不清楚。
贝茜在沿 x 轴正方向移动时,一旦遇到虫洞则必须进入。
现在请你计算,有多少种不同的虫洞配对方案,可以使得贝茜从某个点开始移动,能够陷入到无限循环之中。
输入格式
第一行包含整数 N,表示虫洞数量。
接下来 N 行,每行包含两个整数 x,y,表示一个虫洞的位置坐标。
输出格式
输出一个整数,表示能够使得贝茜陷入无限循环的虫洞配对方案的总数。
数据范围
2≤N≤12,
0≤x,y≤109
输入样例:
4
0 0
1 0
1 1
0 1
输出样例:
2
样例解释:
方案 1:(0,0) 与 (1,0) 配对,(0,1) 与 (1,1) 配对,贝茜从 (−1,0) 出发就可以陷入无限循环。
方案 2:(0,0) 与 (1,1) 配对,(1,0) 与 (0,1) 配对,贝茜从 (1,1) 处进入虫洞,即可陷入 (1,1)→(0,0)→(1,0)→(0,1)→(1,1)… 的无限循环。
算法
所有的配对方式有11 * 9 * 7 * 5 * 3 * 1,共约10395种。思路是检查所有的配对方案是否符合要求。
一个神奇的操作是:将每个点拆成两个点:入点和出点。这里入点和出点有如下的性质:作为入点,出边有且仅有一条;作为出点,最多有一条出边。
因为每个点的出边是唯一的,所以可以将这个图看成是一个有向图。问题就转化为有向图求环问题。可以用tarjan算法,时间复杂度是O(n + m)。因为图中每个点的出边仅有一条,所以这个图要么是一棵树,要么是一个环上挂着一堆树(基环树)。这种图还可以用一个经典的dfs方法判断图中是否存在环。
用used[i]表示点i是否被遍历过,用current[i]表示点i是否在递归栈中。具体找环的做法是:从1到n枚举所有点,当找到一个没有被遍历过的点时,就从该点出发遍历,由于每个点的出边是唯一的,所以我们每次走的时候路径是唯一的(不存在分叉的情况)。边走(dfs递归搜索)边将used[i]、current[i]标记为true,当回溯时,将current[i]标记为false,表示不在递归栈中。如果走到一个已经走过的点(used[i]为true),且该点在递归栈中(current[i]为true),表示找到了环。如果used[i]为true且current[i]为false,则表示没有环,可以终止查找(出边唯一但入边不唯一,表示之前已经从另外一条路沿着这个点往下找过)。因为每个点最多只会被遍历一次,所以时间复杂度是O(n),所以整体时间复杂度是O(方案数 * n)。
C++代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12;
int n;
//ver1[]:纵坐标相同相连的点,ver2[]:经配对相连的点;
int ver1[N], ver2[N], ans;
//st[]:是否配对过
bool st[N], used[N][2], cur[N][2];
struct Point
{
int x, y;
bool operator< (const Point& t) const
{
if (y != t.y) return y < t.y;
return x < t.x;//先纵坐标排序,再横坐标排序
}
}q[N];
bool dfs_c(int a, int b)//找环,a:点,b:出\入
{
if (cur[a][b]) return true;
if (used[a][b]) return false;
cur[a][b] = used[a][b] = true;
bool res = false;
if (!b)//a点是入点,找ver2[a]
{
if (dfs_c(ver2[a], 1)) res = true;
}
else//a点是出点,找横向连接的ver1[a]
{
if (ver1[a] != -1 && dfs_c(ver1[a], 0)) res = true;
}
cur[a][b] = false;
return res;
}
bool check()
{
memset(used, 0, sizeof used);
memset(cur, 0, sizeof cur);
for (int i = 0; i < n; ++i)//遍历所有未找过的点
for (int j = 0; j < 2; ++j)
if (!used[i][j])
if (dfs_c(i, j))//找环
return true;
return false;
}
void dfs(int u)//将点配对
{
if (u == n / 2)//配对完成,检查是否有环
{
if (check()) ans ++;
return;
}
for (int i = 0; i < n; ++i)
if (!st[i])//找第一个还未配对的点i
{
for (int j = i + 1; j < n; ++j)
if (!st[j])//给点i配对
{
st[i] = st[j] = true;
ver2[i] = j, ver2[j] = i;
dfs(u + 1);
ver2[i] = ver2[j] = -1;
st[i] = st[j] = false;
}
break;//第一个还未配对的点i配对完成
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> q[i].x >> q[i].y;
sort(q, q + n);
memset(ver1, -1, sizeof ver1);
memset(ver2, -1, sizeof ver2);
for (int i = 1; i < n; ++i)//建立纵坐标相同的点之间的横向连接
if (q[i].y == q[i - 1].y) ver1[i - 1] = i;
dfs(0);
cout << ans << endl;
return 0;
}