/* Thu Nov 13 21:23:54 JST 2003 : Start */ /* Thu Nov 13 22:29:44 JST 2003 : Accepted? */ #include #include #include #include #include int n; int table[24][24]; /* Taboo... */ bool operator<(const set &x, const set &y) { if (x.size() < y.size()) return true; if (x.size() > y.size()) return false; for (set::iterator i = x.begin(), j = y.begin(); i != x.end() && j != y.end(); i++, j++) { if (*i < *j) return true; if (*i > *j) return false; } return false; } void print_group(set group) { for (set::iterator i = group.begin(); i != group.end(); i++) { if (i != group.begin()) { printf(", "); } printf("%d", *i); } printf("\n"); } set generate_subgroup(int x, int y) { set subgroup1, subgroup2, difference; subgroup1.insert(x); subgroup1.insert(y); subgroup1.insert(table[x][y]); while (1) { difference.clear(); set_difference(subgroup1.begin(), subgroup1.end(), subgroup2.begin(), subgroup2.end(), inserter(difference, difference.begin())); if (difference.empty()) { return subgroup1; } subgroup2 = subgroup1; for (set::iterator i = difference.begin(); i != difference.end(); i++) { for (set::iterator j = subgroup2.begin(); j != subgroup2.end(); j++) { subgroup1.insert(table[*i][*j]); } } } } int main() { int ngroup; char s[1024], *p; set< set > subgroups; gets(s); ngroup = atoi(s); for (int igroup = 0; igroup < ngroup; igroup++) { gets(s); n = atoi(s); for (int i = 0; i < n; i++) { gets(s); p = strtok(s, ","); for (int j = 0; p != NULL; j++) { table[i][j] = atoi(p); p = strtok(NULL, ","); } } subgroups.clear(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { set subgroup; subgroup = generate_subgroup(i, j); if (subgroup.size() < n) { subgroups.insert(subgroup); } } } for (set< set >::iterator i = subgroups.begin(); i != subgroups.end(); i++) { print_group(*i); } printf("*** %d\n", subgroups.size()); } return 0; }