Day 36 | Graph Practice | C++

We have learned some important algorithms of graphs. It is important to take break from learning new stuff and practice what you already know. By practice, I don't mean you go back rot-learn the same thing or solve the same problem. Instead, solve some graph problems randomly and see if it can be solved using what you know (either by yourself or by reading editorial)

If you don't encounter a topic you know during this practice, why care it is less frequent in question set.

Today we will be solving two problem -

Lunar New Year and a Wander

Few observation -

1. Since we want lexicographically smallest order of visits, it will always be best to start from node 1

2. Since we can go to any node but only write when it's unique, we can choose any next node, whose previous node we have visited. In other words, if we are running BFS style traversal, then we can choose any node from queue instead of only front.

3. If we can do point 2, we would choose the minimum thus better to maintain set rather than queue.

We can understand this algorithm by this animation -

We can implement it like this -

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N],ans;
int n,m,a,b,vis[N];
int main(){
  set<int> s;
  cin >> n >> m;
  for(int i = 0; i < m; i++){
     cin >> a >> b;
     g[a].emplace_back(b);
     g[b].emplace_back(a);
  }
  s.emplace(1);
  vis[1] = true;
  while(s.size()){
    int u = *s.begin();
    s.erase(s.begin());
    ans.emplace_back(u);
    for(int i : g[u])
       if(!vis[i])vis[i] = true, s.emplace(i);
  }
  for(int i : ans)cout << i << " ";
 return 0;
}

Building Teams

This is like problems we solved earlier, we store the start of previous connected component and connect our current connected component with it. That's it. Still have a little trouble understanding what I did there, look out example in the GIF below

We can implement it like this -

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

vector<int> vis;
vector<vector<int>> g;

void dfs(int u){
    if(vis[u])return;
    vis[u] = 1;
    for(int v: g[u]){
        dfs(v);
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    
    vis = vector<int> (n+1);
    g = vector<vector<int>> (n+1);
    
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<pair<int,int>> ans;
    int prv = -1;
    for(int i = 1; i <= n; i++){
        if(vis[i])continue;
        if(prv != -1)ans.emplace_back(prv,i);
        prv = i;
        dfs(i);
    }
    
    cout << ans.size() << '\n';
    for(auto i: ans)cout << i.first << " " << i.second << "\n";
    return 0;
}

Please like and share my posts if they are helpful.