Table of Contents
usage instructions
Adjacency method
algorithm
Example
Output
Adjacency list method
in conclusion
Home Backend Development C++ Check if there is a cycle of length 3 in the graph that satisfies the given condition

Check if there is a cycle of length 3 in the graph that satisfies the given condition

Sep 06, 2023 pm 01:01 PM
Check the loop in the graph

Check if there is a cycle of length 3 in the graph that satisfies the given condition

Checks the graph for a loop of length 3 that satisfies the given criteria, preparing to repeatedly traverse each vertex and look at its neighboring vertices. If a vertex has two neighbors that are too connected, a cycle of length 3 exists. This condition guarantees that there is an edge between two neighbors, thus forming a triangle. By filtering all vertices and their neighboring vertices, we will identify whether such a cycle exists. If we find that a vertex has two related neighbors, we can conclude that the graph shows a cycle of length 3 that satisfies the given condition.

usage instructions

  • Adjacency matrix method

  • Adjacency list method

Adjacency method

To check if there is a cycle of length 3 in the graph that satisfies a given condition, we can make use of the contagious method. In this approach, we iterate for each vertex in the graph and check its neighboring vertices. For each vertex, we check whether any two of its neighboring vertices are too closely related. If such a match is found, we check whether the conditions for that match are met. If the condition is met, it indicates a loop of length 3 that is close to satisfying the given condition. By looking at all the vertices in the graph, we can determine if such a cycle exists.

algorithm

  • Initialize the Boolean variable named "cycleExists" to false.

  • Iterate over each vertex in the graph:

    • For each vertex, repeat its adjacent vertices.

    • For each adjacent vertex, emphasize its adjacent vertices (except the current vertex).

    • If any two adjacent vertices are related, continue to the next step.

  • Check whether the combination of associated vertices found in step 2c satisfies the condition.

    • If the condition is met, set "cycleExists" to true and break out of the loop.

  • After completing the cycle, check the value of "cycleExists".

    • If "cycleExists" is true, then there is a cycle of length 3 in the graph that satisfies the given condition.

    • If "cycleExists" is wrong, no such cycle exists.

  • Output results.

  • This calculation repeats the vertices of the graph, analyzes their adjacent vertices, and checks whether any matches of adjacent vertices form a cycle of length 3 that satisfies the given condition.

    李>

Example

#include <iostream>
#include <vector>

using namespace std;

bool checkCycle(vector<vector<int>>& graph, int v, vector<bool>& visited, int parent, int condition) {
    visited[v] = true;

    for (int u : graph[v]) {
        if (!visited[u]) {
            visited[u] = true;

            for (int w : graph[u]) {
                if (visited[w] && w != parent && condition == graph[v][u] + graph[u][w]) {
                    return true;
                }
            }

            visited[u] = false;
        }
    }

    return false;
}

bool hasCycleOfLength3(vector<vector<int>>& graph, int condition) {
    int numVertices = graph.size();
    vector<bool> visited(numVertices, false);

    for (int v = 0; v < numVertices; v++) {
        visited[v] = true;

        for (int u : graph[v]) {
            if (checkCycle(graph, u, visited, v, condition)) {
                return true;
            }
        }

        visited[v] = false;
    }

    return false;
}

int main() {
    int numVertices, numEdges;
    cout << "Enter the number of vertices and edges: ";
    cin >> numVertices >> numEdges;

    vector<vector<int>> graph(numVertices);

    cout << "Enter the connections between vertices (u, v) and their corresponding weights: " << endl;
    for (int i = 0; i < numEdges; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;

        graph[u].push_back(v);
        graph[v].push_back(u);

        // Store the weight/condition between u and v
        graph[u][v] = weight;
        graph[v][u] = weight;
    }

    int condition;
    cout << "Enter the condition to be satisfied: ";
    cin >> condition;

    if (hasCycleOfLength3(graph, condition)) {
        cout << "Cycle of length 3 satisfying the condition exists." << endl;
    } else {
        cout << "Cycle of length 3 satisfying the condition does not exist." << endl;
    }

    return 0;
}


Copy after login

Output

Enter the number of vertices and edges:  
Copy after login

Adjacency list method

Adjacent list methods can be information structures used to talk to the diagram. In this approach, each vertex of the graph is associated with a list containing all its adjacent vertices. To check if there is a cycle of length 3 in the graph that satisfies the given condition, we will iterate over each vertex and its neighboring vertices. For each adjacent vertex, we check if it contains an adjacent vertex in common with the current vertex. If such a common vertex exists, then a ring of length 3 is found. This approach guarantees efficient investigation of the graph by storing essential data about almost all vertices in the infectious list and their associations.

algorithm

  • Make an infectious list that talks to the graph, where each vertex contains a list of its neighboring vertices.

  • Iterate over each vertex in the graph.

  • For each vertex, repeat its adjacent vertices.

  • For each adjacent vertex, emphasize its adjacent vertices (except the current vertex).

  • Check whether there is a common vertex between the current vertex and the adjacent vertex of the adjacent vertex.

  • If a common vertex is found, a cycle of length 3 exists. Return true.

  • If no ring of length 3 is found, return false.

Example

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

bool hasCycleOfLength3(vector<vector<int>>& graph) {
    int n = graph.size();
    
    for (int u = 0; u < n; ++u) {
        unordered_set<int> adjSet(graph[u].begin(), graph[u].end());

        for (int v : graph[u]) {
            for (int w : graph[v]) {
                if (w != u && adjSet.count(w) > 0) {
                    return true; // Cycle of length 3 found
                }
            }
        }
    }

    return false; // No cycle of length 3 found
}

int main() {
    // Create the graph as an adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {0, 2},
        {0, 1, 3},
        {2, 4},
        {3}
    };

    // Check if a cycle of length 3 exists
    bool cycleExists = hasCycleOfLength3(graph);

    // Print the result
    if (cycleExists) {
        cout << "A cycle of length 3 exists in the graph." << endl;
    } else {
        cout << "No cycle of length 3 exists in the graph." << endl;
    }

    return 0;
}
Copy after login

Output

A cycle of length 3 exists in the graph.
Copy after login

in conclusion

This article examines methods for checking whether there is a loop of length 3 in a graph that satisfies a given condition. It illustrates two approaches, specifically the contagious frame approach and the contagious list approach. This article traces the calculation process and gives bits of C code for both methods. The contagious network approach involves emphasizing each vertex and its neighboring vertices to identify cycles of length 3 that satisfy the condition. The contagious list method exploits information structures that talk to the graph and examines common vertices between adjacent vertices to determine the proximity of cycles.

The above is the detailed content of Check if there is a cycle of length 3 in the graph that satisfies the given condition. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

What are the types of values ​​returned by c language functions? What determines the return value? What are the types of values ​​returned by c language functions? What determines the return value? Mar 03, 2025 pm 05:52 PM

This article details C function return types, encompassing basic (int, float, char, etc.), derived (arrays, pointers, structs), and void types. The compiler determines the return type via the function declaration and the return statement, enforcing

Gulc: C library built from scratch Gulc: C library built from scratch Mar 03, 2025 pm 05:46 PM

Gulc is a high-performance C library prioritizing minimal overhead, aggressive inlining, and compiler optimization. Ideal for performance-critical applications like high-frequency trading and embedded systems, its design emphasizes simplicity, modul

What are the definitions and calling rules of c language functions and what are the What are the definitions and calling rules of c language functions and what are the Mar 03, 2025 pm 05:53 PM

This article explains C function declaration vs. definition, argument passing (by value and by pointer), return values, and common pitfalls like memory leaks and type mismatches. It emphasizes the importance of declarations for modularity and provi

C language function format letter case conversion steps C language function format letter case conversion steps Mar 03, 2025 pm 05:53 PM

This article details C functions for string case conversion. It explains using toupper() and tolower() from ctype.h, iterating through strings, and handling null terminators. Common pitfalls like forgetting ctype.h and modifying string literals are

Where is the return value of the c language function stored in memory? Where is the return value of the c language function stored in memory? Mar 03, 2025 pm 05:51 PM

This article examines C function return value storage. Small return values are typically stored in registers for speed; larger values may use pointers to memory (stack or heap), impacting lifetime and requiring manual memory management. Directly acc

distinct usage and phrase sharing distinct usage and phrase sharing Mar 03, 2025 pm 05:51 PM

This article analyzes the multifaceted uses of the adjective "distinct," exploring its grammatical functions, common phrases (e.g., "distinct from," "distinctly different"), and nuanced application in formal vs. informal

How do I use algorithms from the STL (sort, find, transform, etc.) efficiently? How do I use algorithms from the STL (sort, find, transform, etc.) efficiently? Mar 12, 2025 pm 04:52 PM

This article details efficient STL algorithm usage in C . It emphasizes data structure choice (vectors vs. lists), algorithm complexity analysis (e.g., std::sort vs. std::partial_sort), iterator usage, and parallel execution. Common pitfalls like

How does the C   Standard Template Library (STL) work? How does the C Standard Template Library (STL) work? Mar 12, 2025 pm 04:50 PM

This article explains the C Standard Template Library (STL), focusing on its core components: containers, iterators, algorithms, and functors. It details how these interact to enable generic programming, improving code efficiency and readability t

See all articles