Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

qwerty29's blog

By qwerty29, history, 3 months ago, In English,

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!.

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By qwerty29, history, 4 months ago, In English,

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; }

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it