557D Vitaliy and Cycle

Problem - 557D - Codeforces

• 他の人のコードを見て union find を使う方法を知った。グラフの二色塗り分けを union find でやるなんて発想に目から鱗が落ちた。
• 以下は dfs と union find を使う2つの実装。

class Div2D {
public:
    void solve_dfs(void)
    {
            int N, M;
            cin>>N>>M;

            // 1) 3 個の追加ケース
            if ( M == 0 )
            {
                cout<<"3 "<<(ll)N*(N-1)*(N-2)/6<<endl;
                return;
            }

            vector<vector<int>> tree(N);
            UFTree uft(N);
            REP(i, M)
            {
                int a, b;
                cin>>a>>b;
                --a;
                --b;
                tree[a].push_back(b);
                tree[b].push_back(a);
            }
            // グラフに何本か辺を追加して奇数長のサイクルを作る
            // 辺の追加数が最小のとき、追加数と辺の追加方法の数を求める
            //
            // 1) エッジが一つもない点がある
            // odd cycle は 3 点以上含む必要があるので
            //
            // 3 n*(n-1)*(n-2)/6 (=nC3)
            //
            // 2) 全て二点以下からなるグラフ (2点からのグラフが m 個)
            //
            //  A    C      A--C
            //  |    |  =>  | /|   (A->C->B)
            //  B    D      B/ D
            //
            //  2 m*(n-2)
            //
            // 3) 3点以上をもつ連結成分が存在する
            // グラフを二色に塗り分ける
            // (塗り分けられない点がでてくるならそれは長さ 3 以上の odd cycle なので追加の必要なし)
            //
            //  B - W - B - W - B
            //      |
            //      B
            //
            //  B - W - B - W - B
            //    \ |
            //      B
            //
            // nB = #{B}
            // nW = #{W}
            //
            // 1 nB*(nB-1)/2 + nW*(nW-1)/2
            //

            ll way = 0;
            ll maxCnt = 0;
            vector<int> color(N, 0);
            // グラフを二色で塗る
            // 再帰でやると TLE する可能性が高いので stack + loop でやる
            REP(i, N)
            {
                // 彩色済み
                if ( color[i] != 0 )
                    continue;
                ll nB = 0;
                ll nW = 0;
                bool found = false;
                stack<pair<int,int>> stack;
                color[i] = 1;
                stack.emplace(i, 1);
                while ( !stack.empty() )
                {
                    int x, c, nc;
                    tie(x, c) = stack.top();
                    if (c == 1)
                    {
                        nc = -1;
                        ++nW;
                    }
                    else
                    {
                        nc = 1;
                        ++nB;
                    }
                    stack.pop();
                    for (auto y : tree[x])
                    {
                        // found odd cycle
                        if (color[y] == c)
                        {
                            found = true;
                            break;
                        }
                        // 探索済み
                        if (color[y] == nc)
                            continue;
                        color[y] = nc;
                        stack.emplace(y, nc);
                    }
                }
                if ( found )
                {
                    cout<<"0 1"<<endl;
                    return;
                }
                way += (nB*(nB-1)/2 + nW*(nW-1)/2);
                // 連結成分の大きさの最大値を更新しておく
                maxCnt = max(maxCnt, nW+nB);
            }
            // 2) 2 個の追加ですむケース
            if ( maxCnt <= 2 )
            {
                // 2部グラフの数は M になる
                cout<<"2 "<<(ll)M*(N-2)<<endl;
                return;
            }
            cout<<"1 "<<way<<endl;
    }
    void solve_uf(void)
    {
            int N, M;
            cin>>N>>M;
            // 1) 3 個の追加ですむケース
            if ( M == 0 )
            {
                cout<<"3 "<<(ll)N*(N-1)*(N-2)/6<<endl;
                return;
            }
            vector<vector<int>> tree(N);
            // 二色塗り分け
            UFTree uft(2*N);    // 白・黒(+N)2つ分で 2*N
            REP(i, M)
            {
                int a, b;
                cin>>a>>b;
                --a;
                --b;
                tree[a].push_back(b);
                tree[b].push_back(a);
                uft.unite(a,b+N); // a:白 - b:黒
                uft.unite(a+N,b); // a:黒 - b:白
            }
            // a:白 - a:黒 なら奇数長の cycle がある
            REP(i, N) if (uft[i] == uft[i+N])
            {
                cout<<"0 1"<<endl;
                return;
            }
            vector<ll> cnt(2*N, 0);
            // 二色に塗りつぶした頂点を cnt に振り分ける
            REP(i, N) // 白色だけカウント(3 以上の連結成分じゃなければ cnt[i] <= 1)
                ++cnt[uft[i]];
            ll way = 0;
            REP(i, 2*N)
                way += cnt[i]*(cnt[i]-1)/2;
            if (way > 0)
            {
                cout<<"1 "<<way<<endl;
                return;
            }
            // 2頂点or1頂点のグラフしかのこっていない。
            cout<<"2 "<<(ll)(N-2)*M<<endl;
    }
    void solve() {
            solve_uf();
            //solve_dfs();
    }
};