Cycle Detection and Degree Validation

Determining whether a graph contains a cycle can be efficiently achieved using a Disjoint Set Union (DSU) structure. When merging two nodes, if they already share the same root, a cycle exists. Additionally, validating node degrees ensures structural integrity.

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MAX_NODES = 100005;
int parent[MAX_NODES];
int degree[MAX_NODES];
bool cycleFound = false;

int getRoot(int node) {
    if (parent[node] != node) {
        return getRoot(parent[node]);
    }
    return node;
}

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 0; i <= n; ++i) {
        degree[i] = 2;
        parent[i] = i;
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        int rootU = getRoot(u);
        int rootV = getRoot(v);

        if (rootU == rootV) {
            cout << "No" << endl;
            return 0;
        }
        
        parent[rootU] = rootV;
        degree[u]--;
        degree[v]--;
    }

    for (int i = 1; i <= n; ++i) {
        if (degree[i] < 0) {
            cout << "No" << endl;
            cycleFound = true;
            break;
        }
    }

    if (!cycleFound) {
        cout << "Yes" << endl;
    }

    return 0;
}

Counting Valid Triangles in a Dataset

To count the number of valid triangles formed by lengths in an array, one must satisfy the triangle inequality theorem: the sum of any two sides must exceed the third. A brute-force approach checks all triplets, but sorting the array allows for optimization using binary search or two pointers.

Optimized Approach with Binary Search

By sorting the lengths in descending order, for any pair (a, b), we search for the largest (c) such that (b + c > a).

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> lengths(n);

    for (int i = 0; i < n; ++i) {
        cin >> lengths[i];
    }

    sort(lengths.begin(), lengths.end(), greater<int>());

    long long validCount = 0;
    for (int i = 0; i < n - 2; ++i) {
        for (int j = i + 1; j < n - 1; ++j) {
            int left = j + 1;
            int right = n - 1;
            int boundary = -1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (lengths[i] < lengths[j] + lengths[mid]) {
                    boundary = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            if (boundary != -1) {
                validCount += (boundary - (j + 1) + 1);
            }
        }
    }

    cout << validCount << endl;
    return 0;
}

Extracting Cycles in Functional Graphs

In a functional graph where each node points to exact one other node, a cycle is guaranteed. The goal is to identify the nodes forming this cycle. We traverse the path until a visited node is encountered, then isolate the loop segment.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> nextNode(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> nextNode[i];
    }

    vector<int> visited(n + 1, 0);
    vector<int> path;
    int current = 1;

    while (visited[current] == 0) {
        visited[current] = 1;
        path.push_back(current);
        current = nextNode[current];
    }

    vector<int> cycleNodes;
    bool inCycle = false;
    
    for (int node : path) {
        if (node == current) {
            inCycle = true;
        }
        if (inCycle) {
            cycleNodes.push_back(node);
        }
    }

    cout << cycleNodes.size() << endl;
    for (int node : cycleNodes) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Validating Non-Decreasing Sequences under Operations

When transforming an array into a non-decreasing sequence using specific index-based operations, parity plays a crucial role. If the array length is even, its generally possible to satisfy the condition. For odd lengths, we must verify constraints backwards from the end of the array.

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<ll> arr(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    if (n % 2 == 0) {
        cout << "YES\n";
        return;
    }

    ll offset = 0;
    bool possible = true;
    for (int i = n; i >= 2; --i) {
        if (arr[i] + offset < arr[i - 1]) {
            possible = false;
            break;
        }
        if (i % 2 != 0) {
            offset += (arr[i] - arr[i - 1] + offset) / (i - 1);
        }
    }

    if (possible) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Comparative Array Analysis

Comparing two arrays involves checking specific adjacency conditions. Special handling is required for small input sizes. The logic verifies if elements match directly or via neighbors.

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

void runTest() {
    int n;
    cin >> n;
    vector<ll> source(n + 2, 0);
    vector<ll> target(n + 2, 0);

    for (int i = 1; i <= n; ++i) cin >> source[i];
    for (int i = 1; i <= n; ++i) cin >> target[i];

    int result = -1;
    if (n > 2) {
        result = 2;
    }

    for (int i = 1; i <= n; ++i) {
        bool match = (i > 1 && i < n && target[i] == source[i]) || 
                     (target[i] == source[i - 1]) || 
                     (target[i] == source[i + 1]);
        if (match) {
            result = 1;
        }
    }

    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        runTest();
    }
    return 0;
}

Greedy Allocation with Neighbor Constraints

Maximizing the sum of values placed between numbers requires a greedy strategy. Values are allocated to the left first, then the right, ensuring the sum of neighbors does not exceed the current limit minus one.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll> limits(n);
    for (int i = 0; i < n; ++i) {
        cin >> limits[i];
    }

    ll totalSum = 0;
    ll consecutiveCount = 0;
    ll minVal = 2e10;

    for (int i = 0; i < n; ++i) {
        if (limits[i] == 1) {
            consecutiveCount = 0;
            minVal = 2e10;
        } else {
            if (i == 0 || i == n - 1) continue;
            
            consecutiveCount++;
            if (consecutiveCount <= 2) {
                minVal = min(minVal, limits[i]);
            }
            
            if (consecutiveCount >= 2) {
                ll k = min((minVal - 1), (limits[i] - 1));
                totalSum += k;
                minVal = limits[i] - k;
            }
        }
    }

    if (n > 0) {
        if (limits[0] != 1) totalSum += limits[0] - 1;
        if (limits[n - 1] != 1) totalSum += limits[n - 1] - 1;
    }
    
    if (n == 1) {
        totalSum = limits[0] - 1;
    }

    cout << totalSum << endl;
    return 0;
}