提出詳細
ソースコード
#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------------*/
using UnWeightedGraph = vector<vector<int> >;
template<typename G>
struct StronglyConnectedComponents {
const G &g;
UnWeightedGraph gg, rg;
vector<int> comp, order, used;
StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {
for (int i = 0; i < g.size(); i++) {
for (auto e : g[i]) {
gg[i].emplace_back((int) e);
rg[(int) e].emplace_back(i);
}
}
}
int operator[](int k) {
return comp[k];
}
void dfs(int idx) {
if (used[idx]) return;
used[idx] = true;
for (int to : gg[idx]) dfs(to);
order.push_back(idx);
}
void rdfs(int idx, int cnt) {
if (comp[idx] != -1) return;
comp[idx] = cnt;
for (int to : rg[idx]) rdfs(to, cnt);
}
void build(UnWeightedGraph &t) {
for (int i = 0; i < gg.size(); i++) dfs(i);
reverse(begin(order), end(order));
int ptr = 0;
for (int i : order) if (comp[i] == -1) rdfs(i, ptr), ptr++;
t.resize(ptr);
for (int i = 0; i < g.size(); i++) {
for (auto &to : g[i]) {
int x = comp[i], y = comp[to];
if (x == y) continue;
t[x].push_back(y);
}
}
}
};
class Solver {
public:
Solver(int x) {
case(x);
}
void solve() {
int N;
in(N);
vector<string> W(N);
UnWeightedGraph G(N), buff;
in(W);
if (N == 1) {
out(W[0].front() == W[0].back() ? "OK" : "NG");
return;
}
rep(i, N) {
rep(j, N) {
if (i == j) continue;
if (W[i].back() == W[j].front()) {
G[i].pb(j);
}
}
}
StronglyConnectedComponents<UnWeightedGraph> scc(G);
scc.build(buff);
out(buff.size() == 1 ? "OK" : "NG");
}
private:
};
signed main() {
int x;
in(x);
REP(i, 1, x + 1) {
Solver(i).solve();
}
return 0;
}
提出情報
提出出力結果
テストケース情報