Question: https://cses.fi/problemset/task/1628/

You are given an array of n numbers. In how many ways can you choose a subset of the numbers with sum x?

Solution: Using meet in the middle approach but its timing out for few test cases, could you please help me where I can improve my code.

#include <bits/stdc++.h>
#define all(c) (c).begin(), (c).end()
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define fi first
#define se second
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define parr(arr) for(int num : (arr)) cout << num << ' '; cout << '\n';
using namespace std;


int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
        int n; cin >> n;
        long long int x; cin >> x;
        int mid = n/2;
        vector<int> arr(n);
        for(int i=0;i<n;++i) cin >> arr[i];
        vector<long long int> left, right;
        for(int i=0;i<(1<<mid);++i){
            long long int sum = 0;
            for(int j=0;j<32;++j){
                if(i & (1<<j)){
                    sum += arr[j];
                }
            }
            left.push_back(sum);
        }
        int rem = n-mid;
        for(int i=0;i<(1<<rem);++i){
            long long int sum =0;
            for(int j=0;j<32;++j){
                if(i & (1<< j))
                    sum += arr[mid+j];  
            }
            right.push_back(sum);
        }
        long long int count = 0;
        unordered_map<long long int,int> m;
        for(int num : right) m[num]++;
        for(int i=0;i<left.size();++i){
            if(left[i] <= x){
                long long int other = x - left[i];
                count += m[other];
            }
        }
        cout << count << '\n';
    return 0;
}

Question: we are given a graph with some edges non directed. we have to find the direction of those edges such that the graph remains acyclic.

My approach: we have to find the ordering of the visit for each node (topological order). This should be the order for the remaining order as well.

Problem: The below solution is getting TLE. I am not sure where it's failing. the complexity should be the order of the number of nodes in the graph.

Thank you!

#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
using namespace std;

vector<vector<int>> adj;
vector<int> order;
vector<bool> visited;

void dfs(int u){
    for(int v : adj[u]){
        if(!visited[v]){
            visited[v] = true;
            dfs(v);
        }
    }
    order.push_back(u);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while(t--){
        order.clear();
        adj.assign(200001, vector<int>());
        visited.assign(200001,false);
        int n, m; cin >> n >> m;
        int dir, u, v;
        vector<vector<int>> edges;
        for(int i=0;i<m;++i){
            cin >> dir >> u >> v;
            if(dir) adj[u].push_back(v);
            edges.push_back(vector<int>({dir,u,v}));
        }
        for(int i=1;i<=n;++i){
            if(!visited[i]){
                visited[i] = true;
                dfs(i);
            }
        }
        reverse(order.begin(), order.end());
        vector<int> index(n+1);
        for(int i=0;i<order.size();++i) index[order[i]] = i; 
        bool possible = true;
        // for(int i:order) cout << i << ' ';
        // cout << '\n';
        for(vector<int> i : edges){
            int dir = i[0];
            int u = i[1];
            int v = i[2];
            if(dir && index[u] > index[v]){
                cout << "NO\n";
                possible = false;
                break;
            }
        }

        if(possible){
            cout << "YES\n";
            for(int i=0;i<edges.size();++i){
                int dir = edges[i][0];
                int u = edges[i][1];
                int v = edges[i][2];
                if(!dir){
                    if(index[u] < index[v]){
                        cout << u << ' ' << v << '\n';
                    }
                    else{
                        cout << v << ' ' << u << '\n';
                    }
                }
                else{
                    cout << u << ' ' << v << '\n';
                }
            }
        }
    }
    return 0;
}

Problem statement: https://cses.fi/problemset/task/1130/
You are given a tree consisting of n nodes.
A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching?

My Approach:
1) Run BFS to find the bipartite partition for the given tree.
2) We iterate over the number of nodes in the maximum of the above sets.
3) Since every node in this set will have a corresponding node in the other set we can choose this node edge in our answer.
4) while taking the nodes in this set we have to make sure that its neighboring node is only visited once i.e. other nodes in this set cannot share a node in the other set.

#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<vector<int> > graph(n+1);
    
    for(int i=0;i<n-1;++i){
        int a,b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    queue<int> q;
    vector<int> color(n+1);
    vector<int> visited(n+1,0);

    q.push(1);
    color[1] = 0;
    visited[1] = 1;
    while(!q.empty()){
        int node = q.front(); q.pop();
        for(int i:graph[node]){
            if(!visited[i]){
                visited[i] = 1;
                color[i] = (color[node]+1)%2;
                q.push(i);
            }
        }
    }
    vector<int> first;
    vector<int> second;
    for(int i=1;i<=n;++i){
        if(color[i]==0) first.push_back(i);
        else second.push_back(i);
    }
    int count = 0;
    fill(all(visited),0);
    if(first.size() < second.size()) swap(first,second);
    for(int i=0;i<first.size();++i) {
        visited[first[i]] = 1;
        for(int it:graph[first[i]]){
            if(!visited[it]){
                visited[it] = 1;
                count++;
                break;
            }
        }
    }
    cout << count << '\n';
    return 0;
}

Am I going in the right direction for this problem since I am new to this concept?
Thank you!.

Shortest Routes 1 on cses.

Question:
Basically print all the distances from node 1 to all other nodes. We can assume that such a path to all other nodes exists.
The path connecting the nodes is directed and weighted.

My Approach:
1) do dfs and keep updating the node's distance (initialized to LLONG_MAX at the start of search).
2) if the distance to reach a node is greater than the existing distance (previously calculated) then we don't continue the search from that node.
3) sort the edges for each node so that we choose the smallest edge every time.

My Doubt:
1) I am getting TLE for some cases. I wanted to know whether this approach is slow in general or there is some corner case that I am missing, which is getting my code to run in circles.
2) (according to me this should run

My Code:

#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
using namespace std;

void dfs(int node, vector<long long int> &distance, vector<vector<pair<int,long long int> > > &graph){
    for(pair<int,long long int> i:graph[node]){
        if(distance[node]+i.s < distance[i.f]){
            distance[i.f] = distance[node]+i.s;
            dfs(i.f,distance,graph);
        }
    }
}

bool comp(pair<int,long long int> &lhs,pair<int,long long int> &rhs){
    return lhs.f < rhs.f;
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,m; cin >> n >> m;
    vector<vector<pair<int,long long int> > > graph(n+1);
    for(int i=0;i<m;++i){
        int a,b; 
        long long int c; cin >> a >> b >> c;
        graph[a].push_back({b,c});
    }
    for(int i=1;i<=n;++i){
        sort(all(graph[i]),comp);
    }
    vector<long long int> distance(n+1,LLONG_MAX);
    distance[1] = 0;
    dfs(1,distance,graph);
    for(int i=1;i<=n;++i) cout << distance[i] << ' ';
    cout << '\n';
    return 0;
}