1、农夫判断出公共数的条件:所有存在公共数且为一个的数对的值是唯一的。
举例1:奶牛a (1, 2) (3, 4)
奶牛b (1, 5) (3, 4)
(1, 2)与(1, 5)公共数为1
(1, 2)与(3, 4)没有公共数,状态为0
(3, 4)与(1, 5)没有公共数,状态为0
(3, 4)与(3, 4)有两个公共数,应该只有一个公共数,状态为0
所以农夫能判断出公共数为1。
举例2:奶牛a (1, 2) (3, 4)
奶牛b (1, 5) (6, 4)
(1, 2)与(1, 5)公共数为1
(1, 2)与(3, 4)没有公共数,状态为0
(3, 4)与(1, 5)没有公共数,状态为0
(6, 4)与(3, 4)公共数为4
有两个不同的公共数,农夫无法判断。
还有情况是有很多同样的公共数,但农夫不需要知道是哪两个数对,而公共数可以判断出来。
2、奶牛判断出公共数的条件:这头奶牛的任一数对与另一头奶牛的所有数对若存在一个公共数且公共数唯一,则可以判断。
题目要求不论两头奶牛各自拥有哪个数对,都足以令两头奶牛都准确地推断出公共数字。
举例:奶牛a (1, 2) (3, 4)
奶牛b (1, 5) (6, 4)
(1, 2)与(1, 5)公共数为1
(1, 2)与(3, 4)没有公共数,状态为0
奶牛a若数对为(1, 2),则和奶牛b的公共数一定为1
(3, 4)与(1, 5)没有公共数,状态为0
(3, 4)与(6, 4)公共数为4
奶牛a若数对为(3, 4),则和奶牛b的公共数一定为4
同理,奶牛b也一样。
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 15;
int n, m;
int g[N][N]; //保存数对公共数情况,值为数对的公共数,若无公共数或两个公共数,则为0
PII a[N], b[N];
bool check_cow(){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(g[i][j]){
for (int k = 0; k < m; k ++)
if (g[i][k] && g[i][j] != g[i][k]) return false;
for (int k = 0; k < n; k ++)
if (g[k][j] && g[i][j] != g[k][j]) return false;
}
}
}
return true;
}
int check_fammer(){
int state = -1;
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
if (g[i][j] && state == -1) state = g[i][j];
if (g[i][j] && state != g[i][j]) return 0;
}
}
return state;
}
int get_common(PII a, PII b){
if(a == b) return 0;
if(a.x == b.x || a.x == b.y) return a.x;
if(a.y == b.x || a.y == b.y) return a.y;
return 0;
}
int main(){
//输入数据
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
int u, k;
scanf("%d%d", &u, &k);
a[i] = {min(u, k), max(u, k)};
}
for(int i = 0; i < m; i++){
int u, k;
scanf("%d%d", &u, &k);
b[i] = {min(u, k), max(u, k)};
}
//初始化匹配数对公共数状态
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
g[i][j] = get_common(a[i], b[j]);
}
}
//农夫能否判断出公共数,若所有数对的公共数唯一,则公共数为该值,否则无法判断
int f_res = check_fammer();
bool c_res = check_cow();
if(f_res) printf("%d", f_res);
else if (c_res) printf("0");
else printf("-1");
return 0;
}