提出詳細
ソースコード
#include <bits/stdc++.h>
#define int long long
#define REP(i, l, r) REPEAT(i,l,r,true) // [l, r)
#define rep(i, n) REP(i,0,n) // [0, n)
#define REPEAT(i, l, r, condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#ifdef LOCAL
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n, l, r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)
#else
#define show(...) true
#define showlr(n, l, r) true
#endif
#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO puts("NO")
#define No puts("No")
#define no puts("no")
#define case(i) cout<<"Case #"<<i<<":"<<endl
using namespace std;
using vi=vector<int>;
using pint=pair<int, int>;
struct io {
io() {
cin.tie(0);
ios::sync_with_stdio(false);
cout.tie(0);
cout << fixed << setprecision(20);
}
} io;
template<class T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &e:v)is >> e;
return is;
}
template<class T>
ostream &operator<<(ostream &os, vector<T> v) {
os << "{";
for (T &e:v)os << e << (v.size() - (int) (&e - &v[0]) > 1 ? ", " : "");
os << "}";
return os;
}
void _DEBUG() {}
template<typename H, typename... T>
void _DEBUG(H a, T...b) {
cerr << a << (sizeof...(b) ? "," : "\n");
_DEBUG(b...);
}
inline void in() {}
template<typename H, typename... T>
void in(H &a, T &... b) {
cin >> a;
in(b...);
}
inline void out() {}
template<typename H, typename... T>
void out(H a, T... b) {
cout << a << (sizeof...(b) ? " " : "\n");
out(b...);
}
template<class T>
void resz(int n, T &v) { v.resize(n); }
template<class H, class... T>
void resz(int n, H &a, T &... b) {
a.resize(n);
resz(n, b...);
}
template<typename V, typename H>
void resize(vector<V> &v, const H a) { v.resize(a); }
template<typename V, typename H, typename... T>
void resize(vector<V> &v, const H &a, const T... b) {
v.resize(a);
for (auto &v:v) resize(v, b...);
}
const int INF = 1LL << 55;
const int MOD = 1000000007;
const double EPS = 1e-8;
/*------------end of definitions------------*/
class UnionFind {
public:
/**
* コンストラクタ．
* @param n
*/
UnionFind(int n);
/**
* n要素で初期化
* @param n
* @return
*/
UnionFind init(int n);
/**
* 木の根を求める
* @param x
* @return
*/
int find(int x);
/**
* xとyの属する集合を併合する
* @param x
* @param y
*/
void unite(int x, int y);
/**
* xとyが同じ集合に属するか否か
* @param x
* @param y
* @return
*/
bool same(int x, int y);
private:
/**
* 親
*/
std::vector<int> par;
/**
* 木の深さ
*/
std::vector<int> rank;
};
UnionFind::UnionFind(int n) {
par.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
}
}
UnionFind UnionFind::init(int n) {
return UnionFind(n);
}
// 木の根を求める
int UnionFind::find(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = find(par[x]);
}
}
// xとyの属する集合を併合する
void UnionFind::unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y])rank[x]++;
}
}
// xとyが同じ集合に属するか否か
bool UnionFind::same(int x, int y) {
return find(x) == find(y);
}
class Solver {
public:
Solver(int x) {
case(x);
}
void solve() {
int N;
in(N);
vector<string> W(N);
in(W);
map<char, int> I, O;
set<int> exist;
UnionFind uf(26);
for (auto e: W) {
I[e.front()]++;
O[e.back()]++;
uf.unite(e.front() - 'a', e.back() - 'a');
exist.insert(e.front() - 'a');
exist.insert(e.back() - 'a');
}
REP(i, 'a', 'z') {
if (I[i] != O[i]) {
out("NG");
return;
}
}
rep(i, 26) {
rep(j, 26) {
if (exist.find(i) != exist.end() && exist.find(j) != exist.end()) {
if (!uf.same(i, j)) {
out("NG");
return;
}
}
}
}
out("OK");
}
private:
};
signed main() {
int x;
in(x);
REP(i, 1, x + 1) {
Solver(i).solve();
}
return 0;
}
提出情報
提出出力結果
テストケース情報
京都産業大学コンピュータ理工学部