cormoran's note


cormoran

競技プログラミング・電子工作・ロボットなどで遊びます



Recent Post




AOJ-0225-Kobutanukitsuneko

AOJ 0225 Kobutanukitsuneko

有向グラフ上でオイラー閉路を求める問題に落ちる

問題概要

N個文字列が与えられる。しりとりをする。

N個全てを使ってしりとりができ、さらにそのしりとりの最初の文字列の先頭と、最後の文字列の最後尾の文字の一致するようにできるか判定せよ。

(できるなら”OK”,できないなら”NG”)

解法

a-zまでをラベルとした点を作り、

N個の文字列それぞれの先頭の文字から後尾の文字の点へと有向辺を張る。

このグラフでオイラー閉路が存在するか調べれば良い。

条件は、

  • 全ての点で、それぞれの入次数と出次数が等しい
  • グラフが連結

自分は最初、1つ目にはすぐに気づいたが、グラフとして捉えられていなかったせいで二つ目の条件がもっと複雑な感じの何かになるのではないか…みたいに考えてちょっと時間がかかった。(反省)

グラフの連結性は、今回の場合は好きな1点から始めてすべての点に行けるかどうか判定すればいい。


#include<iostream>
#include<vector>
#include<cassert>
#include<string>
#include<set>
using namespace std;

typedef long long ll;
typedef ll int__;
#define rep(i,j) for(int__ i=0;i<(int__)(j);i++)
#define repeat(i,j,k) for(int__ i=(j);i<(int__)(k);i++)

const int alpha_size = 'z' - 'a' + 1;

void visit(int now, vector<bool> &visited, const vector<set<int>> &E){
    visited[now] = true;
    for(int nxt : E[now]){
        if(not visited[nxt]){
            visit(nxt, visited, E);
        }
    }
}

bool solve(){
    int N; cin >> N;
    if(N == 0) return false;
    vector<int> d(alpha_size);
    vector<set<int>> E(alpha_size);
    rep(i, N){
        string s; cin >> s;
        int f = s.front() - 'a';
        int b = s.back() - 'a';
        ++d[f];
        --d[b];
        E[f].insert(b);
    }
    vector<bool> visited(alpha_size);
    rep(i, E.size()){
        if(E[i].size() > 0){
            visit(i, visited, E);
            break;
        }
    }
    bool flg = true;
    rep(i, alpha_size){
        if(d[i] != 0 or  (E[i].size() > 0 and not visited[i])) flg = false;
    }
    cout << (flg ? "OK" : "NG") << endl;
    
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}


comments powered by Disqus