Chaque maison de la colonie a au plus un tuyau qui y entre et au plus un tuyau qui en sort. Les réservoirs et les robinets doivent être installés de manière à ce que chaque maison avec un tuyau sortant mais pas de tuyau entrant obtienne un réservoir installé sur son toit et chaque maison avec seulement un tuyau entrant et aucun tuyau sortant ait un robinet.

Étant donné deux entiers n et p désignant le nombre de maisons et le nombre de tuyaux. Les connexions de tuyau entre les maisons contiennent trois valeurs d'entrée : a_i , b_i , d_i désignant le tuyau de diamètre d_i de la maison a_i à la maison b_i , découvrez la solution efficace pour le réseau. 

La sortie contiendra le nombre de paires de réservoirs et de robinets t installés en première ligne et les t lignes suivantes contiennent trois nombres entiers : le numéro de maison du réservoir, le numéro de maison du robinet et le diamètre minimum du tuyau entre eux.

Exemples: 

Entrée :  4 2
        1 2 60
        3 4 50
Sortie : 2
        1 2 60
        3 4 50
Explication :
Les composants connectés sont : 1->2 et 3->4
Par conséquent, notre réponse est 2 suivi de 1 2 60 et 3 4 50.

Entrée : 9 6
       7 4 98
       5 9 72
       4 6 10
       2 8 22
       9 7 17
       3 1 66
Sortie : 3
        2 8 22
        3 1 66
        5 6 10
Explication :
Les composants connectés sont 3->1, 5->9-> 7->4->6 et 2->8 . 
Par conséquent, notre réponse est 3 suivi de 2 8 22, 3 1 66, 5 6 10

Approcher: 

• Effectuez DFS à partir des maisons appropriées pour trouver tous les différents composants connectés. Le nombre de composants connectés différents est notre réponse t. 
• Les t lignes suivantes de la sortie sont le début du composant connecté, la fin du composant connecté et le diamètre minimum du début à la fin du composant connecté dans chaque ligne. 
• Étant donné que les réservoirs ne peuvent être installés que sur les maisons ayant un tuyau sortant et aucun tuyau entrant, ce sont donc des maisons appropriées pour démarrer le DFS, c'est-à-dire effectuer le DFS à partir de ces maisons non visitées.

Vous trouverez ci-dessous la mise en œuvre de l'approche ci-dessus :

vector<int> a;

vector<int> b;

vector<int> c;

 

int ans;

 

int dfs(int w)

{

    if (starting_vertex_of_pipes[w] == 0)

        return w;

    if (diameter_between_two_pipes[w] < ans)

        ans = diameter_between_two_pipes[w];

    return dfs(starting_vertex_of_pipes[w]);

}

 

// Function performing calculations.

void solve(int arr[][3])

{

    for (int i = 0; i < number_of_pipes; ++i) {

 

        int house_1 = arr[i][0], house_2 = arr[i][1],

            pipe_diameter = arr[i][2];

 

        starting_vertex_of_pipes[house_1] = house_2;

        diameter_between_two_pipes[house_1] = pipe_diameter;

        ending_vertex_of_pipes[house_2] = house_1;

    }

 

    a.clear();

    b.clear();

    c.clear();

 

    for (int j = 1; j <= number_of_houses; ++j)

 

        /*If a pipe has no ending vertex

        but has starting vertex i.e is

        an outgoing pipe then we need

        to start DFS with this vertex.*/

        if (ending_vertex_of_pipes[j] == 0

            && starting_vertex_of_pipes[j]) {

            ans = 1000000000;

            int w = dfs(j);

 

            // We put the details of component

            // in final output array

            a.push_back(j);

            b.push_back(w);

            c.push_back(ans);

        }

 

    cout << a.size() << endl;

    for (int j = 0; j < a.size(); ++j)

        cout << a[j] << " " << b[j] << " " << c[j] << endl;

}

 

// driver function

int main()

{

    number_of_houses = 9, number_of_pipes = 6;

 

    memset(ending_vertex_of_pipes, 0,

           sizeof(ending_vertex_of_pipes));

    memset(starting_vertex_of_pipes, 0,

           sizeof(starting_vertex_of_pipes));

    memset(diameter_between_two_pipes, 0,

           sizeof(diameter_between_two_pipes));

 

    int arr[][3]

        = { { 7, 4, 98 }, { 5, 9, 72 }, { 4, 6, 10 },

            { 2, 8, 22 }, { 9, 7, 17 }, { 3, 1, 66 } };

 

    solve(arr);

    return 0;

}

Production

3
2 8 22
3 1 66
5 6 10