rendered paste body#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>using namespace std;struct Node { char label; char neighbour[5][150]; int ptr[5];};struct Edge { char nodeA; char nodeB; int weight;};char table1[110][110];char table2[110][110];char line[20000];int count1[26];int count2[26];Node nodes1[110];Node nodes2[110];Edge edges1[15000];Edge edges2[15000];int n, m;int nedge1, nedge2;bool operator==(Edge& a, Edge& b) { return a.weight == b.weight && a.nodeA == b.nodeA && a.nodeB == b.nodeB;}bool operator==(Node& a, Node& b) { bool equal_label = a.label == b.label; bool equal_neighbours = true; for (int i = 0; i < 5; i++) { if (a.ptr[i] != b.ptr[i]) { equal_neighbours = false; break; } else { for (int j = 0; j < a.ptr[i]; j++) { if (a.neighbour[i][j] != b.neighbour[i][j]) { equal_neighbours = false; break; } } } } return equal_label && equal_neighbours;}int cmp(const void *a, const void *b) { char *c = (char *) a; char *d = (char *) b; return *c - *d;}int cmp2(const void *a, const void *b) { Node *c = (Node *) a; Node *d = (Node *) b; if (c->label < d->label) return -1; else { if (c->label > d->label) return 1; else { int tmp; for (int i = 0; i < 5; i++) { if ((tmp = strcmp(c->neighbour[i], d->neighbour[i])) != 0) return tmp; } } } return 0;}int cmp3(const void *a, const void *b) { Edge *c = (Edge *) a; Edge *d = (Edge *) b; if (c->weight < d->weight) return -1; else { if (c->weight > d->weight) return 1; else { if (c->nodeA < d->nodeA) return -1; else { if (c->nodeA > d->nodeA) return 1; else { if (c->nodeB < d->nodeB) return -1; else { if (c->nodeB > d->nodeB) return 1; else return 0; } } } } }}void einlesen() { char *c, *d; char c1; nedge1 = nedge2 = 0; for (int i = 0; i < 26; i++) { count1[i] = count2[i] = 0; } cin >> n; memset(nodes1, 0, n * sizeof(Node)); while ((c1 = getchar()) != '\n'); for (int i = 0; i < n; i++) { fgets(line, 20000, stdin); c = strtok(line, " \n\r\t"); int j = 0; do { table1[i][j] = c[0]; j++; } while ((c = strtok(NULL, " \n\r\t"))); table1[i][i+1] = '\0'; count1[table1[i][i]-'A']++; } cin >> m; memset(nodes2, 0, m * sizeof(Node)); while ((c1 = getchar()) != '\n'); for (int i = 0; i < m; i++) { fgets(line, 20000, stdin); d = strtok(line, " \n\r\t"); int j = 0; do { table2[i][j] = d[0]; j++; } while ((d = strtok(NULL, " \n\r\t"))); table2[i][i+1] = '\0'; count2[table2[i][i]-'A']++; } for (int i = 0; i < n; i++) { nodes1[i].label = table1[i][i]; for (int j = i-1; j >= 0; j--) { switch (table1[i][j]) { case '0': break; case '1': nodes1[i].neighbour[1][nodes1[i].ptr[1]++] = table1[j][j]; nodes1[j].neighbour[1][nodes1[j].ptr[1]++] = table1[i][i]; edges1[nedge1].nodeA = table1[i][i]; edges1[nedge1].nodeB = table1[j][j]; edges1[nedge1].weight = 1; nedge1++; edges1[nedge1].nodeA = table1[j][j]; edges1[nedge1].nodeB = table1[i][i]; edges1[nedge1].weight = 1; nedge1++; break; case '2': nodes1[i].neighbour[2][nodes1[i].ptr[2]++] = table1[j][j]; nodes1[j].neighbour[2][nodes1[j].ptr[2]++] = table1[i][i]; edges1[nedge1].nodeA = table1[i][i]; edges1[nedge1].nodeB = table1[j][j]; edges1[nedge1].weight = 2; nedge1++; edges1[nedge1].nodeA = table1[j][j]; edges1[nedge1].nodeB = table1[i][i]; edges1[nedge1].weight = 2; nedge1++; break; case '3': nodes1[i].neighbour[3][nodes1[i].ptr[3]++] = table1[j][j]; nodes1[j].neighbour[3][nodes1[j].ptr[3]++] = table1[i][i]; edges1[nedge1].nodeA = table1[i][i]; edges1[nedge1].nodeB = table1[j][j]; edges1[nedge1].weight = 3; nedge1++; edges1[nedge1].nodeA = table1[j][j]; edges1[nedge1].nodeB = table1[i][i]; edges1[nedge1].weight = 3; nedge1++; break; case '4': nodes1[i].neighbour[4][nodes1[i].ptr[4]++] = table1[j][j]; nodes1[j].neighbour[4][nodes1[j].ptr[4]++] = table1[i][i]; edges1[nedge1].nodeA = table1[i][i]; edges1[nedge1].nodeB = table1[j][j]; edges1[nedge1].weight = 4; nedge1++; edges1[nedge1].nodeA = table1[j][j]; edges1[nedge1].nodeB = table1[i][i]; edges1[nedge1].weight = 4; nedge1++; break; } } } for (int i = 0; i < m; i++) { nodes2[i].label = table2[i][i]; for (int j = i-1; j >= 0; j--) { switch (table2[i][j]) { case '0': break; case '1': nodes2[i].neighbour[1][nodes2[i].ptr[1]++] = table2[j][j]; nodes2[j].neighbour[1][nodes2[j].ptr[1]++] = table2[i][i]; edges2[nedge2].nodeA = table2[i][i]; edges2[nedge2].nodeB = table2[j][j]; edges2[nedge2].weight = 1; nedge2++; edges2[nedge2].nodeA = table2[j][j]; edges2[nedge2].nodeB = table2[i][i]; edges2[nedge2].weight = 1; nedge2++; break; case '2': nodes2[i].neighbour[2][nodes2[i].ptr[2]++] = table2[j][j]; nodes2[j].neighbour[2][nodes2[j].ptr[2]++] = table2[i][i]; edges2[nedge2].nodeA = table2[i][i]; edges2[nedge2].nodeB = table2[j][j]; edges2[nedge2].weight = 2; nedge2++; edges2[nedge2].nodeA = table2[j][j]; edges2[nedge2].nodeB = table2[i][i]; edges2[nedge2].weight = 2; nedge2++; break; case '3': nodes2[i].neighbour[3][nodes2[i].ptr[3]++] = table2[j][j]; nodes2[j].neighbour[3][nodes2[j].ptr[3]++] = table2[i][i]; edges2[nedge2].nodeA = table2[i][i]; edges2[nedge2].nodeB = table2[j][j]; edges2[nedge2].weight = 3; nedge2++; edges2[nedge2].nodeA = table2[j][j]; edges2[nedge2].nodeB = table2[i][i]; edges2[nedge2].weight = 3; nedge2++; break; case '4': nodes2[i].neighbour[4][nodes2[i].ptr[4]++] = table2[j][j]; nodes2[j].neighbour[4][nodes2[j].ptr[4]++] = table2[i][i]; edges2[nedge2].nodeA = table2[i][i]; edges2[nedge2].nodeB = table2[j][j]; edges2[nedge2].weight = 4; nedge2++; edges2[nedge2].nodeA = table2[j][j]; edges2[nedge2].nodeB = table2[i][i]; edges2[nedge2].weight = 4; nedge2++; break; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < 5; j++) { nodes1[i].neighbour[j][nodes1[i].ptr[j]] = 0; qsort(nodes1[i].neighbour[j], nodes1[i].ptr[j], sizeof(char), cmp); } } for (int i = 0; i < m; i++) { for (int j = 0; j < 5; j++) { nodes2[i].neighbour[j][nodes2[i].ptr[j]] = 0; qsort(nodes2[i].neighbour[j], nodes2[i].ptr[j], sizeof(char), cmp); } } qsort(nodes1, n, sizeof(Node), cmp2); qsort(nodes2, m, sizeof(Node), cmp2); qsort(edges1, nedge1, sizeof(Edge), cmp3); qsort(edges2, nedge2, sizeof(Edge), cmp3);}bool vergleiche() { if (n != m) return false; if (nedge1 != nedge2) return false; for (int i = 0; i < 26; i++) { if (count1[i] != count2[i]) return false; } for (int i = 0; i < n; i++) { if (!(nodes1[i] == nodes2[i])) return false; } for (int i = 0; i < nedge1; i++) { if (!(edges1[i] == edges2[i])) return false; } return true;}int main() { int tests; cin >> tests; for (int i = 0; i < tests; i++) { einlesen(); if (vergleiche()) cout << "identical" << endl; else cout << "not identical" << endl; } return 0;}