1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
bool pair_exist(int left, int right, int b[], int sizeOfB)
{
for (int i=0; i<sizeOfB; i+=2)
{
if (left==b[i] && right==b[i+1]) return true;
}
return false;
}
bool transitive(int b[], int sizeOfB)
{
for (int i=0; i<sizeOfB; i+=2)
{
int e = b[i];
int f = b[i+1];
// we've chosen pair (e, f) from b
// we now find any (f, g)
for (int j=0; j<sizeOfB; j+=2)
{
if (i == j) continue; // avoid choosing same pair
if (b[j] != f) continue; // ignore all pairs not having f for 1st value.
// we now have a pair (b[j], b[j+1]) where f is the 1st value
// thus b[j+1] = g
// therefore we must now see if (e, g) is a pair in b
if (!pair_exist(e, b[j+1], b, sizeOfB)) return false;
}
}
return true;
}
void main()
{
int b[] = {1, 2, 2, 3, 4, 5, 7, 9, 1, 3};
bool is_transitive = transitive(b, sizeof(b)/sizeof(int));
cout << is_transitive << endl;
}
| |