Problem analysis of Help Amanda

PROBLEM: HELP AMANDA

Amanda's problem can be easily solved using depth first search (DFS).
In fact, finding connectivity and cyclicity is one of the applications of DFS.


PSEUDOCODES:

// To find cyclicity
#define CON_A MAT[src][i] == 1
#define CON_B src != i
#define CON_C (i is visited)
#define CON_D tos >= 2
#define CON_E stack.elementAt(tos-2) != i


void dfs(int src) {
    source is marked as visited.
    stack.push(source)
    for(int i = 0; i < nodes; i++) {
        if(CON_A && CON_B && CON_C && CON_D && CON_E) {
            cyclic = 1;
        }
        if(adj[src][i] == 1 && s[i] == 0) {
            dfs(i);
        }
    }
    top--;
}

/* stack.elementAt(tos-2) != i means to say that the vertex visited just immediately is not i. since a cycle has at least 3 vertices. */
// so if tos-2 is not i and i is visited, it means there is a cycle.


// TO FIND CONNECTIVITY

dfs(src)

void isConnected(void) {
    for(int i = 0; i < nodes; i++)
        if(s[i] == 0) {
            connected = false;
            return;
        }
}