ARC041 D問題 辺彩色

考察系の問題。
辺を順番に塗っていき、折り返してもう一度塗り直すことができる。

こういうときの常套手段として、過去から遡れば、辺の彩色は一度でいいという、つまり塗り直す必要は無いという性質がある。また、これより、分岐の時も何も考えなくていいこともわかる。

また、奇数長の閉路があればどんな風にも塗ることができる。赤と青を一つずつずらしてもう一度塗れるからだ。奇数長の閉路の判定は、"二部グラフを構成していって、構成できれば奇数長さ"、という判定法と、"ある頂点からのdistを保存していって、点が重なったところでそのときのdistを比較して差が奇数ならば奇数長"という判定法があるっぽい。
とりあえず前者で実装をした。

const int MAX_V = 2002;
struct edge{int to; int color; int index;};
vector<edge> G[MAX_V];
int usedV[MAX_V];
bool usedE[MAX_V];
int N, M;

bool dfs(int s, int c){
    if(usedV[s] != -1 && usedV[s] != c){
        return true;
    }
    usedV[s] = c;
    bool res = false;
    for(auto& e : G[s]){
        if(usedE[e.index]) continue;
        if(e.color == c){
            usedE[e.index] = true;
            res |=dfs(e.to, (c+1)%2);
        }else{
            continue;
        }
    }
    return res;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a,b; char c; cin >> a >> b >> c;
        a--; b--;
        G[a].push_back(edge{b, (c == 'r'?1:0), i});
        G[b].push_back(edge{a, (c == 'r'?1:0), i});
    }

    for(int i=0; i<N; i++){
        memset(usedV, -1, sizeof(usedV));
        memset(usedE, false, sizeof(usedE));
        bool res = dfs(i, G[i][0].color);
        if(res){
            cout << "Yes" << endl;
            return 0;
        }else{
            bool ok = true;
            for(int j=0; j<M; j++){
                if(!usedE[j]){ ok = false; break; }
            }
            if(ok){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}