UTPC 2012 C問題

Tatsuya Yatagawa

2012-12-08

さて続いてはC問題です。これは僕は当日は解けなかった。

この問題の難しいところは、N、Mともに100000なので、まともに隣接行列を持ったのではメモリが全然足りないというところ。まぁ、ここまでは少し考えればわかります。

そこで隣接が途切れているところだけをsetなりmapなりで持つことを考えるわけですが、今度はデータが増えてくると隣接頂点の探索に時間がかかりすぎてTLEになってしまいます。

最大のポイントは、Nが450以上の時は、すべてnoになるというところにあります。ノード数がNの無向グラフに閉路が存在しない（この問題ではこれを「森」と言っている）場合、実はエッジの数はたかだかN-1本であることが知られています（僕は知らなかったけど）。

ということは、初期の完全グラフのエッジの数 N(N-1)/2 からMの最大値である100000を引いたものがN-1より大きくなる場合には、そのそもどうがんばっても閉路が存在してしまうわけです。そうなる最小のNを二次不等式で求めると450になります。ですからNが450以上の場合はそもそも考える必要がないわけです。

あとは450×450の情報を隣接行列として持って万事解決！と思ったのですが、これを単なる配列として持ってしまうと、深さ優先探索で閉路を探すときにfor文を回す回数が多すぎてTLEになってしまう！！（僕の書き方が悪いだけ？）

なので、各ノードごとに自分と隣接している頂点をsetに保存して無駄な繰り返し処理を省いています。これで何とか1.6秒ぐらいにおさまった。やれやれ。

#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <limits.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <stack>
using namespace std;

typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPA(i,s,e) for(int i=s; i<=e; i++)
#define REPD(i,s,e) for(int i=s; i>=e; i--)

template <typename T> inline T tmax(T t1, T t2) { return t1 > t2 ? t1 : t2; }
template <typename T> inline T tmin(T t1, T t2) { return t1 < t2 ? t1 : t2; }

const size_t N_MAX = 455;

vector<bitset<N_MAX> > G;
vector<set<int> > E;
bitset<N_MAX> V;

int N, M, S, T;

bool check(int p, int k) {
    V.set(k);
    set<int>::iterator it;
    for(it=E[k].begin(); it != E[k].end(); ++it) {
        if(p == (*it)) continue; // skip if i is parent
        if(k == (*it)) continue; // skip if i is itself 
        if(!G[k][(*it)]) continue; // edge k-i not exist
        
        if(V[(*it)]) return false;
        if(!check(k, (*it))) return false;
    }

    return true;
}

int main() {
    cin >> N >> M;

    // 実はNは450以上にはなりえない
    if(N>=450) {
        REP(i,M) cout << "no" << endl;
        return 0;
    }

    int ne = (N * N - N) / 2;

    // グラフの作成
    G = vector<bitset<N_MAX> >(N_MAX);
    E = vector<set<int> >(N_MAX);
    REP(i,N_MAX) REPA(j,1,N) E[i].insert(j);
    REP(i,N_MAX) G[i].set();
    REP(i,M) {
        cin >> S >> T;
        if(G[S][T]) {
            ne--;
            E[S].erase(T);
            E[T].erase(S);
        } else {
            ne++;
            E[S].insert(T);
            E[T].insert(S);
        }

        G[S][T] = ~G[S][T];
        G[T][S] = ~G[T][S];
    
        if(ne > N-1) {
            cout << "no" << endl;
            continue;
        }

        // 訪れた場所を表すテーブルの初期化
        V.reset();

        // グラフが森かどうかを判定
        int m = 0;
        bool a = true;
        while(m < N) {
            m++;
            if(V[m]) {
                continue;
            }

            if(!check(-1, m)) {
                a = false;
                break;
            }
        }

        printf(a ? "yes\n" : "no\n");
    }
}