URI Online Judge Solution 1081 || DFSr - Depth Hierarchy

URI Online Judge | 1081

DFSr - Depth Hierarchy

By Neilor Tonin, URI  Brazil

Timelimit: 1

In graphs, the PathR function is well-known. It's called dfs or dfsr. It means a recursive deph-searching in nodes of a graph, using backtracking. The task here is, from an input graph, generate the hierarquie design of the searched nodes. To help you, is given the PathR procedure, listed above.

Input

The input file contains many test cases. The first line of the input file contains an integer N  that represents the quantity of test cases that follows. Each one of N test cases contains, in the first line, two informations: (1 ≤ V ≤ 20) and E (1 ≤ E ≤ 20), that are respectively the amount of vertices and edges of the graph. Follow E lines containing informations over all of the edges of this graph.

Output

For each test case, an output must be printed that represents a depth search for all nodes, with respect of the hierarquie of each of them. The character b means a blank space. See the follewing example:
bb0-2 pathR(G,2)
bbbb2-1 pathR(G,1)
bbbb2-4 pathR(G,4)
bbbbbb4-1

And so on...
Obs.: The program should print a blank line after each test case, even after the last test case.

Input Sample	Output Sample
2 12 9 0 1 1 5 5 6 0 4 4 2 2 3 7 8 1 7 10 11 11 8 0 1 1 2 3 4 4 3 5 6 6 8 7 9 9 10	Caso 1:   0-1 pathR(G,1)     1-5 pathR(G,5)       5-6 pathR(G,6)     1-7 pathR(G,7)       7-8 pathR(G,8)   0-4 pathR(G,4)     4-2 pathR(G,2)       2-3 pathR(G,3)   10-11 pathR(G,11) Caso 2:   0-1 pathR(G,1)     1-2 pathR(G,2)   3-4 pathR(G,4)     4-3   5-6 pathR(G,6)     6-8 pathR(G,8)   7-9 pathR(G,9)     9-10 pathR(G,10)

URI Online Judge Solution 1081 || DFSr - Depth Hierarchy solution in C++

#include <cstdio>

#include <cstring>

#include <iostream>

 

using namespace std;

 

#define MAX 20

#define sc(a) scanf("%d", &a);

#define sc2(a, b) scanf("%d%d", &a, &b);

 

bool disc[MAX];

int graph[MAX][MAX];

 

void clean(int v) {

    int i, j;

    for (i = 0; i < v; i++) {

        for (j = 0; j < v; j++)

            graph[i][j] = 0;

        disc[i] = false;

    }

}

 

bool dfs(int v, int n, int s) {

    int i;

    bool path = false;

 

    disc[v] = true;

 

    for (i = 0; i < n; i++) {

        if (graph[v][i] == 1) {

            path = true;

            if (!disc[i]) {

                cout << string(s, ' ');

                printf("%d-%d pathR(G,%d)\n", v, i, i);

                dfs(i, n, s + 2);

            } else {

                cout << string(s, ' ');

                printf("%d-%d\n", v, i);

            }

        }

    }

 

    return path;

}

 

void dfs_runner(int v) {

    int i, ind = 0;

 

    while (1) {

        if (dfs(ind, v, 2))

            puts("");

 

        ind = -1;

 

        for (i = 0; i < v; i++) {

            if (!disc[i]) {

                ind = i;

                break;

            }

        }

 

        if (ind == -1)

            break;

    }

}

 

int main(int argc, char const *argv[]) {

    int n, v, e, o, d, c = 1;

    sc(n);

 

    while(n--) {

        sc2(v, e);

        clean(v);

 

        while(e--) {

            sc2(o, d);

            graph[o][d] = 1;

        }

 

        printf("Caso %d:\n", c++);

        dfs_runner(v);

    }

 

    return 0;

}

See or download code from dropbox
See in URI