CSES :: Graph Algorithms :: Building Roads

Problem : Please find the problem here.

Explanation : Given a graph structure, number of roads here is basically the minimum edges required to make this graph connected. This is intern equal to number of connected components in the graph.
Save any one node from each connected components and print the path in between those nodes.

Code : Used DFS to find connected components.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

void DFS(int u, map<int, set<int>> &adj, vector<bool> &vis) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v]) {
            DFS(v, adj, vis);
        }
    }
}

vector<int> countRoads(int n, map<int, set<int>> &adj, vector<bool> &vis) {
    vector<int> roads;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            DFS(i, adj, vis);
            roads.emplace_back(i);
        }
    }

    return roads;
}

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


    int n, m, a, b;
    cin >> n >> m;

    map<int, set<int>> adj;
    for (int i = 0; i < m; i++) {
        cin >> a >> b; a--, b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }

    vector<bool> vis(n, 0);
    vector<int> result = countRoads(n, adj, vis);

    cout << result.size()-1 << '\n';
    for (int i = 1; i < (int)result.size(); i++) {
        cout << result[0]+1 << ' ' << result[i]+1 << '\n';
    }
    return 0;
}

CSES :: Graph Algorithms :: Message Routes

Problem : Please find the problem here.

Explanation : Travese Graph with BFS to get shortest path between starting and end point And save the parent of each node in an array to backtrack the path between two given points.

Code : Used BFS to traverse the graph.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

bool checkPath(int start, int end, map<int, set<int>> &adj, vector<int> &vis, vector<int> &p) {
    queue<int> qu;
    qu.push(start);
    vis[start] = 1;

    while (qu.size()) {
        int u = qu.front(); qu.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                p[v] = u;
                vis[v] = 1;
                qu.push(v);
            }
        }
    }

    return vis[end];
}

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

    int n, m, x, y;
    cin >> n >> m;

    int a = 0, b = n-1;
    map<int, set<int>> adj;
    vector<int> p(mxN), vis(mxN, 0);

    for (int i = 0; i < m; i++) {
        cin >> x >> y; x--, y--;
        adj[x].insert(y);
        adj[y].insert(x);
    }

    if (checkPath(0, n-1, adj, vis, p)) {
        vector<int> pathNodes;

        while (a != b) {
            pathNodes.emplace_back(b);
            b = p[b];
        }
        pathNodes.emplace_back(a);
        reverse(pathNodes.begin(), pathNodes.end());
        cout << pathNodes.size() << '\n';

        for (int x : pathNodes) {
            cout << x+1 << ' ';
        }
    }
    else {
        cout << "IMPOSSIBLE";
    }
    return 0;
}

CSES :: Range Queries :: Static Range Minimum Queries

Problem : Please find the problem here.

Explanation : Save array into a tree where array elements are at the leaves. And each node will represent the minimum of the elements of its childrens.

Code : Used segment tree.

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

void construct(vector<ll> &tree, vector<ll> &arr, int start, int end, int node) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }

    int mid = (start+end) >> 1;
    int leftNode = node << 1;
    int rightNode = leftNode + 1;
    construct(tree, arr, start, mid, leftNode);
    construct(tree, arr, mid+1, end, rightNode);

    tree[node] = min(tree[leftNode], tree[rightNode]);
}

int query(vector<ll> &tree, int start, int end, int l, int r, int node) {
    if (r < start || end < l) return INT_MAX;
    if (l <= start && end <= r) return tree[node];

    int mid = (start+end) >> 1;
    int leftNode = node << 1;
    int rightNode = leftNode + 1;

    int leftResult = query(tree, start, mid, l, r, leftNode);
    int rightResult = query(tree,  mid+1, end, l, r, rightNode);

    return  min(leftResult, rightResult);
}

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


    int n, q, l, r;
    cin >> n >> q;
    
    vector<ll> arr(n), tree(4*n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    construct(tree, arr, 0, n-1, 1);

    while (q--) {
        cin >> l >> r;
        cout << query(tree, 0, n-1, l-1, r-1, 1) << '\n';
    }
    
    return 0;
}

CSES :: Introductory Algorithms :: Missing Number

Problem : Please find the problem here.

Explanation : Apply XOR of all n-1 numbers with numbers between 1 to n.

Code : missing number = (1^2^....^n) ^ (a[0]^a[1]^...a[n-1])

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

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

    int n, x;
    cin >> n;
    ll res = 0;
    for (int i = 0; i < n-1; i++) {
        cin >> x;
        res ^= x;
    }
    for (int i = 1; i <= n; i++) {
        res ^= i;
    }

    cout << res;
    return 0;
}

CSES :: Introductory Problems :: Repetitions

Problem : Please find the problem here.

Explanation : Read the string and keep the count of consecutive equal characters. Update this count on finding the different char and start over.

Code :

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    int mxCount = INT_MIN, count = 1;
    for (int i = 1; i < s.length(); i++) {
        if (s[i] == s[i-1]) {
            count++;
        } else {
            mxCount = max(count, mxCount);
            count = 1;
        }
    }

    mxCount = max(count, mxCount);

    cout << mxCount;

    return 0;
}