提出詳細
ソースコード
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)
template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x) cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//edit
struct SCC {
int V;
vector<vector<int> > G;//グラフの隣接リスト表現
vector<vector<int> > rG;//変の向きを逆にしたグラフ
vector<int> vs;//帰りがけ順の並び
vector<bool> used;//既に調べたか
vector<int> cmp;//属する共連結成分のトポロジカル順序
SCC(int v) {
V = v;
G.resize(V);
rG.resize(V);
used.resize(V);
cmp.resize(V);
}
/**
* 辺を貼る
* @param from 辺の元
* @param to 辺の先
*/
void add_edge(int from, int to) {
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v) {
used[v] = true;
for (int i = 0; i < G[v].size(); i++) {
if (!used[G[v][i]]) dfs(G[v][i]);
}
vs.push_back(v);
}
void rdfs(int v, int k) {
used[v] = true;
cmp[v] = k;
for (int i = 0; i < rG[v].size(); i++) {
if (!used[rG[v][i]]) rdfs(rG[v][i], k);
}
}
int scc() {
fill(used.begin(), used.end(), false);
vs.clear();
for (int v = 0; v < V; v++) {
if (!used[v]) dfs(v);
}
fill(used.begin(), used.end(), false);
int k = 0;
for (int i = vs.size() - 1; i >= 0; i--) {
if (!used[vs[i]]) rdfs(vs[i], k++);
}
return k;
}
};
class Solve {
public:
void solve() {
Int N;
cin >> N;
vector<string> vs(N);
SCC scc(26);
for (int i = 0; i < N; ++i) cin >> vs[i];
vector<Int> in(26), out(26);
set<Int> st;
for (auto e : vs) {
in[e.front() - 'a']++;
out[e.back() - 'a']++;
scc.add_edge(e.back() - 'a', e.front() - 'a');
st.insert(e.back() - 'a');
st.insert(e.front() - 'a');
}
int k = scc.scc();
vector<Int> diff(26);
for (int i = 0; i < 26; ++i) {
diff[i] = out[i] - in[i];
}
if (*min_element(all(diff)) == 0 && *max_element(all(diff)) == 0) {
for (auto e : st) {
if (scc.cmp[e] != scc.cmp[*st.begin()]) {
cout << "NG" << endl;
return;
}
}
cout << "OK" << endl;
return;
}
if (*min_element(all(diff)) < -1 || *max_element(all(diff)) > 1) {
cout << "NG" << endl;
return;
}
Int p = 0, m = 0;
Int s, t;
for (int i = 0; i < 26; ++i) {
if (diff[i] == 1) {
p++;
s = i;
}
if (diff[i] == -1) {
m--;
t = i;
}
}
if (p == 1 && m == 1 && scc.cmp[s] == 0 && scc.cmp[t] == 1) {
cout << "OK" << endl;
return;
}
cout << "NG" << endl;
return;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
Int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
cout << "Case #" << i << ":" << endl;
Solve().solve();
}
return 0;
}
提出情報
提出出力結果
テストケース情報
京都産業大学コンピュータ理工学部