The idea is quite simple. Since the graph may consist of multiple connected components, we need to ensure that we iterate each component individually. Run DFS or BFS on each unvisited node, keeping track of the parent of each node and marking it as visited. If you visit a node that has already been visited and it is not your parent, this implies that the graph contains a cycle.

Link: https://ideone.com/0pn6Dl

Link: https://ideone.com/TWYllE

In this problem, it was necessary to calculate the degrees of each vertex and find the answer. Note that since n  > = 4 , m  > = 3 and the graph is connected, the answer is unambiguous.

1) all degrees 2 and two vertices have degree 1 — a tire.

2) all degrees 2 — a ring.

3) all degrees 1 and one has degree  > 2 — a star.

4) otherwise unknown.

Link: https://ideone.com/om9eh7

The straightforward solution is to sort the array and loop through the largest $$$k$$$ elements. This runs in O($$$n\log n$$$) time and uses O($$$n$$$) memory, but it likely won't pass due to the space constraints. Can we do better? Do we really need all the elements, or just the largest $$$k$$$?

We only need the largest $$$k$$$ elements, so we can ignore the smallest $$$n-k$$$. To do this, build a min-heap and keep inserting elements. Once the heap size reaches $$$k+1$$$, use peek to remove the smallest element. Repeat this process until all elements are processed so we end up having the largest $$$k$$$ elements. The space complexity is O($$$k$$$) and the time complexity is O($$$n\log n$$$).

A min-heap is a type of priority queue. However, for this problem, you should build the heap from scratch as instructed. You can use pre-built min-heaps in future solutions.

#include<bits/stdc++.h>
using namespace std;

int n,m,k;

cin >> n >> k;

priority_queue<int,vector<int>, greater<int>> q;

while(n--){
    cin >> m;

    q.push(m);

    if(q.size()>k)q.pop();
}

long long answ = 0;

while(q.size()){
    int c = q.top();q.pop();

    answ += c;
}

cout << answ << '\n';

This is a classic interval scheduling problem, and the solution involves sorting by the second value (ending time). The approach is straightforward:

• Sort the movies by their ending times.

• Start by picking the movie that ends the earliest.

• After picking a movie, skip all movies that overlap with it.

• Keep repeating this process by selecting the next movie that ends the earliest and doesn't overlap with the last chosen movie.

This way, you maximize the number of non-overlapping movies you can select

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
    if(a.second == b.second){
        return a.first < b.first;
     }
    return (a.second < b.second);
}


int n;

cin >> n;

vector<pair<int,int>> v(n);

int answ = 1,last = 0;

for(int i = 0;i<n;i++) cin >> v[i].first >> v[i].second;

sort(v.begin(),v.end(),sortbysec);

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

    if(v[i].f >= v[last].s){
        answ++;last = i;
    }
}


cout << answ << '\n';

excepted_sum = n*(n+1)/2

answer = n*(n+1)/2 — sum(Array)

For c++ users use long long, and for java users use long to avoid overflow

What is the maximum sum we can obtain if we have even number of negative integers?

What about odd number of negative integers?

What is the maximum number of negative integers we may have in an optimal sequence?