Count ST

Soal#

Informasi#

• Sumber: CompFest7 - Final CPC Senior
• Tanggal: 2015-10-03

Arsip#

• TLX

Ringkasan#

Diberikan sebuah graf kaktus (cactus graph). Tentukan banyaknya kemungkinan pohon merentang minimum (minimum spanning tree) dari graf tersebut, modulo $10^9 + 7$.

Solusi#

Petunjuk#

Pembahasan#

Sedikit catatan, dikatakan pada soal bahwa kita harus mencari banyaknya pohon merentang minimum pada graf kaktus di mana bobot dari semua sisinya (edge-nya) sama. Maka, itu sama saja dengan mencari banyaknya pohon merentang tanpa mempedulikan apakah hasilnya minimum atau tidak.

Membentuk sebuah pohon merentang dari sebuah graf dapat kita lihat sebagai operasi untuk menghapus sebanyak-banyaknya sisi sehingga graf tersebut masih terhubung dan menjadi sebuah pohon. Setiap sisi pada graf kaktus dapat dikategorikan menjadi dua: tidak berada dalam siklus atau berada dalam sebuah siklus.

Dengan jelas, saat kita menghapus satu sisi yang tidak berada dalam siklus, graf akan menjadi tidak terhubung. Jadi, kita tidak boleh menghapus sisi ini. Sisi ini dikenal sebagai bridge dalam teori graf.

Sebaliknya, saat kita menghapus satu sisi dalam siklus, graf akan masih terhubung. Butuh menghapus setidaknya dua sisi dalam siklus agar membuat graf menjadi tidak terhubung. Banyaknya kemungkinan sisi yang bisa dihapus dari sebuah siklus sama dengan banyaknya sisi atau simpul (vertex) yang terdapat pada siklus tersebut.

Jawaban akhir didapatkan dengan mengalikan banyaknya sisi yang bisa dihapus dari semua siklus, modulo $10^9 + 7$.

Solusi awal yang saya buat secara garis besar dapat dibagi menjadi dua langkah: mencari semua bridge lalu menelusuri semua siklus sambil menghitung jawaban akhir.

Untuk mencari bridge, saya menggunakan algoritma Tarjan dengan sedikit modifikasi.

Untuk menelusuri semua siklus, saya melakukan prosedur DFS (depth-first search) yang dimulai dari sembarang simpul. Awalnya, simpul tersebut saya beri ID dengan nilai 0. Saat berada pada suatu simpul $u$, saya menandai $u$ sebagai berada di dalam stack prosedur DFS. Penandaan ini berfungsi untuk menentukan apakah prosedur telah menemukan simpul awal dari sebuah siklus. Kemudian, saya mengunjungi semua tetangga $v$ dari $u$, kecuali yang terhubung dengan bridge. Apabila $v$ tidak memiliki ID (belum pernah dikunjungi), maka $v$ akan diberi ID dengan nilai lebih satu dari nilai ID simpul $u$ dan melanjutkan prosedur DFS dari simpul $v$. Apabila $v$ berada dalam stack, maka kita telah menemukan simpul awal dari siklus yang saat ini kita telusuri. Oleh karena itu, kita kalikan banyaknya simpul dalam siklus (yang didapat dengan bantuan dari nilai ID) saat ini dengan jawaban akhir. Setelah kita selesai melakukan prosedur DFS dari $u$, tandai $u$ sebagai tidak berada di dalam stack.

Dengan adanya bridge, kita bisa saja tidak mengunjungi semua simpul untuk mendapatkan semua siklus yang terdapat dalam graf. Oleh karena itu, kita lakukan prosedur DFS secara berulang untuk setiap simpul yang belum kita kunjungi.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long int lli;

lli T, N, M, Ai, Bi, idx, ans, k = 1E9 + 7;
vector <int> al[50000];
map < pair <int, int >, bool> bridge;
int id[50000];
int lowlink[50000];
bool onstack[50000];

void dfs(int u, int pred = -1){
    id[u] = lowlink[u] = idx++;
    onstack[u] = 1;

    for(int v : al[u]){
        if(v == pred){
            continue;
        }

        if(!onstack[v]){
            dfs(v, u);
            lowlink[u] = min(lowlink[u], lowlink[v]);

            if(lowlink[v] > id[u]){
                bridge[make_pair(min(u, v), max(u, v))] = 1;
            }
        }
        else{
            lowlink[u] = min(lowlink[u], id[v]);
        }
    }
}

void sfd(int u, int pred = -1){
    onstack[u] = 1;

    for(int v : al[u]){
        if(v == pred || bridge[make_pair(min(u, v), max(u, v))]){
            continue;
        }

        if(id[v] == -1){
            id[v] = id[u] + 1;
            sfd(v, u);
        }
        else{
            if(onstack[v]){
                ans = (ans * (id[u] - id[v] + 1)) % k;
            }
        }
    }

    onstack[u] = 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--){
        cin >> N >> M;

        for(int i = 0; i < M; i++){
            cin >> Ai >> Bi;

            al[Ai].push_back(Bi);
            al[Bi].push_back(Ai);
        }

        for(int i = 0; i < N; i++){
            id[i] = lowlink[i] = -1;
            onstack[i] = 0;
        }

        idx = 0;
        dfs(0);

        for(int i = 0; i < N; i++){
            id[i] = -1;
            onstack[i] = 0;
        }

        ans = 1;
        idx = 0;
        for(int i = 0; i < N; i++){
            if(id[i] == -1){
                id[i] = 0;
                sfd(i);
            }
        }

        cout << ans << '\n';

        for(int i = 0; i < N; i++){
            al[i].clear();
        }
        bridge.clear();
    }
    return 0;
}

Setelah saya pikirkan ulang, kita tidak perlu bergantung pada bridge untuk mencari jawaban akhir. Oleh karena itu, langkah untuk mencari bridge dapat kita hilangkan sepenuhnya. Prosedur DFS juga hanya dilakukan sekali saja karena kita bisa mengunjungi semua simpul tanpa mempedulikan bridge.

Kode#

#include <iostream>
#include <vector>
using namespace std;
typedef long long int lli;

const lli MOD = 1E9 + 7;

lli T, N, M, Ai, Bi, ans;
vector <int> al[50000];
int id[50000];
bool onstack[50000];

void dfs(int u, int pred = -1){
    onstack[u] = 1;

    for(int v : al[u]){
        if(v == pred){
            continue;
        }

        if(id[v] == -1){
            id[v] = id[u] + 1;
            dfs(v, u);
        }
        else if(onstack[v]){
            ans = (ans * (id[u] - id[v] + 1)) % MOD;
        }
    }

    onstack[u] = 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--){
        for(int i = 0; i < N; i++){
            al[i].clear();
        }
        
        cin >> N >> M;

        for(int i = 0; i < M; i++){
            cin >> Ai >> Bi;

            al[Ai].push_back(Bi);
            al[Bi].push_back(Ai);
        }

        for(int i = 0; i < N; i++){
            id[i] = -1;
            onstack[i] = 0;
        }

        ans = 1;
        id[0] = 0;
        dfs(0);

        cout << ans << '\n';
    }
    return 0;
}