mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #309 (Div. 1) C. Love Triangles

CodeForces

これも考察が結構深くて面白かったです。

問題

Problem - C - Codeforces

解法

uwiさんのつぶやきを参考にして考えました(途中から考え方がずれてきてる気がしますが)。

とりあえず「最終的にクリーク2個以下にならなきゃいけない」というところを考えてみましょう。
グラフ理論において,グラフGの部分グラフCがクリークとは,C上のすべての頂点が,自分以外のCの頂点全てと連結していることを言います。完全グラフの部分グラフバージョンみたいな感じですね。

また,この問題において,頂点v, uが連結している必要十分条件は,vとuがloveの関係にあることを言います。

これを元に「最終的にクリーク2個以下にならなきゃいけない」をイメージ化すると以下のとおりです。確かにそうならないとダメっぽいですね(証明も図を見れば簡単に示せそうな気がする)。

f:id:mayokoex:20150625184808j:plain
f:id:mayokoex:20150625184818j:plain

ということで,loveの関係にある頂点同士をunionFindなどで結びつけると,それぞれのグループはクリークでなければならないことがわかります(これは最後のNGの例を見ればわかると思います)。同じグループでa[i], b[i]についてc[i] == 0となるものがあったら答えは0です。

unionFindでグループが出来たとします。クリークは最大で2つまでに圧縮しないといけないので,今度はそれぞれのグループを合併することを考えましょう。

やはり写真最後のNGの例により,グループ同士でhateの関係が一つでもある物同士を同じクリークとして合併することは出来ません。とりあえずこのhateの関係が一つでもあるグループ同士を辺で結んだ新しいグラフを考えます。

このように合併してはいけないクリーク同士の情報を集めていくと,もしかしたらクリークの数が2より大きくならざるを得ない状態になるかもしれません(例えばa, b, cというグループがあって,aとbは合併できない,bとcは合併できない,cとaは合併できない,という状態になると,結局a, b, cという3つのクリークが必要になるが,これは条件に合わない)。

こんな感じで答えが0になる可能性はどのように判定できるかというと,この「グループ同士の関係を表したグラフ」が二部グラフになっているかどうかで判定することが出来ます。

以上の可能性を考慮してすべて大丈夫だった場合,「どのようにクリーク同士をつなげるか」というのが答えです。
これには再びunionFindが活躍します。辺で結ばれたグループ同士をさらに大きな同じグループとみなして2^(グループの数-1)を求めれば良いです。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

const int MAXN = 100100;
const ll MOD = 1e9+7;
int n, m;
int a[MAXN], b[MAXN], c[MAXN];
UnionFind uf;
vector<int> G[MAXN];
int color[MAXN];

bool dfs(int cur, int c) {
    color[cur] = c;
    for (int v : G[cur]) {
        if (color[v] == c) return false;
        if (color[v] == -c) continue;
        if (!dfs(v, -c)) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    uf.init(n+10);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        if (c[i] == 1) {
            uf.unite(a[i], b[i]);
        }
    }
    for (int i = 0; i < m; i++) {
        if (c[i] == 0) {
            if (uf.same(a[i], b[i])) {
                cout << 0 << endl;
                return 0;
            }
        }
    }
    map<int, int> M;
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (M.find(uf.find(i)) == M.end()) M.insert(make_pair(uf.find(i), k++));
    }
    for (int i = 0; i < m; i++) {
        if (c[i] == 0) {
            G[M[uf.find(a[i])]].push_back(M[uf.find(b[i])]);
            G[M[uf.find(b[i])]].push_back(M[uf.find(a[i])]);
        }
    }
    for (int i = 0; i < k; i++) {
        sort(G[i].begin(), G[i].end());
        G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
    }
    for (int i = 0; i < k; i++) {
        if (color[i] == 0) if (!dfs(i, 1)) {
            cout << 0 << endl;
            return 0;
        }
    }
    UnionFind uu(k);
    for (int i = 0; i < m; i++) {
        if (c[i] == 0) uu.unite(M[uf.find(a[i])], M[uf.find(b[i])]);
    }
    ll ans = 1;
    for (int i = 0; i < uu.count()-1; i++) (ans *= 2) %= MOD;
    cout << ans << endl;
    return 0;
}