4
\$\begingroup\$

The question is this one on UVa, and it basically gives us n, the number of dominoes and (a,b) relations such that pushing a will cause b to fall down too. First t, the test cases is inputted and then number of vertices and edges, and the (a,b) relations.


My approach

My approach was I first run a dfs on the graph (till all elements are reached) and maintain an array that shows when each vertex was reached [somewhat inspired from Kosaraju's algo for SCCs]. If a->b->c is my dfs tree, reached[c] will be equal to 3, reached[b] be 2, and reached[a] be 1. This step is O(vertices+edges).

Then I run DFSs from vertices starting from those with minimum reached value. Every time the DFS runs, I increment a counter. This is also O(vertices+edges).


I tried for smaller test cases and got the right answer, but submitting on UVa gives me TLE. I don't know if my logic is wrong or if my implementation is messed up somewhere. The code is here:

#include<bits/stdc++.h>
using namespace std;

int n,counter,reached[100002],visited[100002],visiting[100002];
void dfs(int u,vector< vector<int> > graph){
    visiting[u]++;
    for(auto const& i:graph[u]){
        if(!visiting[i])
            dfs(i,graph);
    }
    visited[counter]=u;
    counter--;
}
void dfs2(int u,vector< vector<int> > graph){
    reached[u]++;
    for(auto const& i:graph[u]){
        if(!reached[i])
            dfs2(i,graph);
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(visiting,0,sizeof visiting);
        memset(visited,0,sizeof visited);
        cin>>n;
        vector< vector<int> > graph(n+1);
        int m;
        counter=n;
        cin>>m;
        while(m--)
        {
            int a,b;
            cin>>a>>b;
            graph[a].push_back(b);
        }
        int mcounter=0;
        for(int i=1;i<n+1;i++)if(!visiting[i])dfs(i,graph);
        memset(reached,0,sizeof reached);
        for(int i=1;i<n+1;i++){
            if(!reached[visited[i]]){
                dfs2(visited[i],graph);
                mcounter++;
            }
        }
        cout<<mcounter<<'\n';
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ What is REP?.. \$\endgroup\$ – vnp Dec 20 '16 at 21:10
  • \$\begingroup\$ @vnp sorry about that, changed it \$\endgroup\$ – Indo Ubt Dec 20 '16 at 21:38
1
\$\begingroup\$

Alternate algorithm

I would suggest the following:

  1. After reading the list of domino dependencies, you should be able to compute a set of "root" dominos. A "root" domino is simply a domino that is not pushed by any other domino.
  2. Each root domino must be pushed, since there is no other domino to push it. So for each root domino, push it, and do a dfs to mark all dominos knocked down by it.
  3. After step #2, there may be dominos left standing. These dominos must either be part of a cycle, or hanging off of a cycle.
  4. For each remaining domino, do a dfs on it, looking for a cycle.
  5. If the domino did not cycle, then do not increment the push count, but mark all the dominos in the dfs as knocked over. This was a domino hanging off a cycle, and you know that this domino's parent(s) will eventually get knocked over by some other push.
  6. If the domino did cycle, then keep a list of each domino that was part of its cycle (note that there could be more than one cycle through the same domino). After doing the dfs and marking all dominos as knocked down, go through the list of dominos that were part of its cycle. If any of them have a parent that is still standing, then do not increment the push count. The reason is that the still standing parent will get pushed by some other domino, and it will knock down this whole cycle. In other words, if a cycle of dominos has an external parent, then it can be ignored because the push from another cycle that triggers the external parent will knock down this cycle.

I haven't actually written a program to test this algorithm, so there could be a flaw in my logic dealing with cycles. But I think it should work, and it should be fast because you never process a node more than once.

\$\endgroup\$
  • \$\begingroup\$ I have an idea for another algorithm that basically finds SSCs and adds to a counter for all SSCs that do not have an indegree. I'm fairly sure that works too. But I'm wondering why my current algo gives TLE. Thanks \$\endgroup\$ – Indo Ubt Dec 21 '16 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.