範例程式碼 uva11175
//uva11175
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n, m, k, node1, node2, len, flag;
cin >> n;
string output;
for (int i = 1; i <= n; ++i) {
cin >> m;
cin >> k;
vector< vector<int> > forward(m);
vector< vector<int> > back(m);
vector< vector<bool> > is_same(m, vector<bool>(m, true));
for (int j = 0; j < k; ++j) {
cin >> node1 >> node2;
forward[node1].push_back(node2);
back[node2].push_back(node1);
}
for (int j = 0; j < m; ++j)
sort(forward[j].begin(), forward[j].end());
for (int x = 0; x < m - 1; ++x) {
for (int y = x + 1; y < m; ++y) {
if (forward[x] != forward[y]) {
is_same[x][y] = false;
is_same[y][x] = false;
}
}
}
for (int j = 0; j < m; ++j) {
flag = 1;
len = back[j].size();
for (int x = 0; x < len - 1; ++x) {
for (int y = x + 1; y < len; ++y) {
node1 = back[j][x];
node2 = back[j][y];
if (!is_same[node1][node2]) {
flag = 0;
break;
}
}
if (flag == 0)
break;
}
if (flag == 0)
break;
}
output = (flag == 1)? "Yes":"No";
cout << "Case #" << i << ": " << output << "\n";
vector< vector<int> >().swap(forward);
vector< vector<int> >().swap(back);
vector< vector<bool> >().swap(is_same);
}
return 0;
}