Solution UVA: 11504 - Dominos

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11504 - Dominos	Accepted	C++11	0.560	0.010	3605	46 secs ago

Suggestion: (version Vietnamese at the end of blog)

This problem is the problem of counting the number of strongly connected components in a DIRECTED graph. To solve this problem, we have two approaches:

Approach 1: Topo sort the graph and then count the number of connected components as in an UNDIRECTED graph.

Approach 2: Find the strongly connected components and color them. After coloring them, we iterate through each vertex and check the following conditions:

If the color of vertex u is different from the color of vertex v (vertices u and v belong to different strongly connected components)

AND

If fall[the color of vertex v] is false (the dominos belonging to this strongly connected component have not fallen)

=> Then we decrease the SCC count by 1 and set fall[the color of vertex v] to true (knock down the dominos of this color)

(Explanation: Vertices with the same color belong to the same strongly connected component, SCC is the number of strongly connected components in the graph, v is a vertex adjacent to u)

Finally, we print the result, which is SCC.

To make it easier to understand, I will draw an illustrative picture: Let's assume we have 4 strongly connected components and we only need to knock down dominos 3 times (first knock down the red dominos, knock down the blue dominos (the yellow dominos will fall along), and finally knock down the green dominos).

 

- I study strongly connected components at link (vietnamese). You can try or look up from internet (only need know to use template is easy to solve problem)

Here is my code using Approach 2:

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1000100;

int n, m;

int timeDfs = 0, scc = 0;

int low[maxN], num[maxN];

bool deleted[maxN];

vector <int> g[maxN];

stack <int> st;

bool fall[maxN];

unordered_map<int, bool> have[maxN];

int color[maxN];

void dfs(int u) {

    num[u] = low[u] = ++timeDfs;

    st.push(u);

    for (int v : g[u]) {

        if (deleted[v]) continue;

        if (!num[v]){

            dfs(v);

            low[u] = min(low[u], low[v]);

        }

        else low[u] = min(low[u], num[v]);

    }

    if (low[u] == num[u]) {

        scc++;

        color[u]= low[u];

        int v;

        do {

            v = st.top();

            color[v]= color[u];

            st.pop();

            deleted[v] = true;

        }

        while (v != u);

    }

}

void toColor(int u){

   

    for (int v : g[u])

        if (color[v] != color[u] and not fall[color[v]]){

            fall[color[v]]= true;

            scc--;

        }

             

}

int main() {

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t;  cin >> t;

    while(t--){

        cin >> n >> m;

       

        timeDfs= 0, scc= 0;

        for(int i=1; i<=n; i++) g[i].clear(), color[i]=0, low[i]=0, num[i]=0, deleted[i]=false, fall[i]=false, have[i].clear();

       

         

        for (int i = 1; i <= m; i++) {

            int u, v;

            cin >> u >> v;

            if (have[u][v]) continue;  

            have[u][v]= true;

            g[u].push_back(v);

        }

        for (int i = 1; i <= n; i++)

            if (!num[i]) dfs(i);

           

        for (int i = 1; i <= n; i++)

            toColor(i);

        cout<<scc<<"\n";

    }

}

Gợi ý:

Bài toán này chính là bài toán đếm số thành phần liên thông trong đồ thị CÓ hướng, để giải bài này ta có 2 cách:

- Cách 1: Sắp xếp topo và sau đó tìm số thành phần liên thông GIỐNG trong đồ thị VÔ hướng

Đoạn code của tôi sử dụng cách 2:

- Cách 2: Tìm các thành phần liên thông MẠNH và tô màu chúng. Sau khi đã tô màu chúng ta duyệt từng đỉnh và kiểm tra như sau:

+ Nếu màu đỉnh u khác với màu đỉnh v  (hai đỉnh u, v thuộc 2 thành phần liên thông mạnh khác nhau)

VÀ 

+ Nếu fall[màu của đỉnh v] bằng false (các domino thuộc thành phần liên thông mạnh này chưa bị đỗ) 

=> Thì ta giảm SCC đi 1 và cho fall[màu của đỉnh v] là true (lật đỗ các dominos có màu này)

(Giải thích: Các đỉnh cùng màu sẽ là các đỉnh trong cùng một thành phần liên thông mạnh, SCC là số thành phần liên thông mạnh của đồ thị, v là đỉnh kề với u)

Cuối cùng chúng ta in kết quả là SCC

Để dễ hiểu hơn tôi sẽ vẽ một hình ảnh minh họa: Giả sử ta có 4 thành phần liên thông mạnh và ta chỉ cần 3 lần lật ngã dominos (lần 1 lật đổ các dominos đỏ, lật đổ các dominos xanh dương (các dominos vàng sẽ bị ngã theo), và cuối cùng lật đổ dominos màu xanh lá cây)