Hi everyone,
This is a continuation of the Live DSA learning sessions being conducted as part of the DSA Learning series.
A session would generally be conducted by CodeChef volunteers and would be a live discussion (via text + video). The main purpose of these sessions would be to discuss the theory topics and then move on how to go about solving the problems of the contest.
For Contest 8, the 2nd session is as follows:
-
Topic: Theory discussion of Graph Theory Basics + Live problem solving of 1 - 2 problems of the contest 8 + QnA
-
Brief Description:
We will primarily be discussing more complicated variants of BFS and Dijkstra (BFS/Dijkstra tree, multi-source shortest path, etc.). Furthermore, we will explore sample problems based on these topics. -
Pre-requisite:
Recommended having gone through the reading material of this week here -
Session volunteer:
Sidhant Bansal -
Date-Time:
12:00 PM IST, 1st August 2020 (Saturday) -
Duration:
2 hours -
Platform for video conferencing:
Zoom Meetings limited 100 seats. Entry to the session on Zoom will be on a first come first serve basis.
Rest of the participants can join live on CodeChef’s YouTube channel . -
To register:
If you are interested just register by clicking on the Going button below the topic title at the top and Add it to your calendar for a reminder so that you don’t miss it
-
Note from CodeChef:
— These sessions are hosted by our volunteers. Kindly respect their efforts and time.
— In case of any doubts, please post in the comments.
[Update 1]
Zoom meeting Details -
Topic: [OFFICIAL] DSA Learning Series Live Session - Graph Theory Basics - Contest 8 - Session 13
Time: Aug 1, 2020 12:00 PM India
Join Zoom Meeting
Meeting ID: 872 0898 1439
Passcode: 523896
[Update 2]
Catch us live on YouTube here -
[Update 3]
Things discussed:
Standard BFS:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> adj[N];
bool vis[N];
int d[N];
int main() {
int n, m, u, v;
cin>>n>>m;
while(m--) {
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(vis, 0, sizeof(vis));
queue<int> Q;
int src = 1;
d[src] = 0;
vis[src] = 1;
Q.push(src);
while(!Q.empty()) {
u = Q.front();
Q.pop();
for(auto v : adj[u]) {
if (vis[v] == 0) {
d[v] = d[u] + 1;
vis[v] = 1;
Q.push(v);
}
}
}
}
BFS on 2d grid:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
string A[N];
int r, c;
int d[N][N];
queue<pair<int, int> > Q;
bool valid(int x, int y) {
return (x >= 0 and x < r and y >= 0 and y < c and A[x][y] != '#');
}
int main() {
memset(d, -1, sizeof(d));
pair<int, int> desti;
cin>>r>>c;
for(int i = 0; i < r; i ++) {
cin>>A[i];
for(int j = 0; j < c; j++) {
if(A[i][j] == 'F') {
Q.push({i, j}); // push dummy node to F (for all F's)
d[i][j] = 0;
} else if(A[i][j] == 'P')
desti = {i, j};
// else ./#
}
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
while(!Q.empty()) {
pair<int, int> u = Q.front();
Q.pop();
int x = u.first, y = u.second;
for(int i = 0; i < 4; i++) {
if(valid(x + dx[i], y + dy[i]) and d[x + dx[i]][y + dy[i]] == -1)
{
d[x + dx[i]][y + dy[i]] = d[x][y] + 1;
Q.push({x + dx[i], y + dy[i]});
}
}
}
cout<< d[desti.first][desti.second] << endl;
}
Standard Djikstra
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<pair<int, int> > adj[N];
bool vis[N];
int d[N];
// to make it min-heap instead of max
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
int main() {
int n, m, u, v, w;
cin>>n>>m;
while(m--) {
cin>>u>>v;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
memset(vis, 0, sizeof(vis));
for(int i = 1; <= n; i++) d[i] = INT_MAX;
int src = 1;
d[src] = 0;
Q.push({0, src});
while(!Q.empty()) {
u = Q.front().second;
Q.pop();
if(vis[u]) continue; // skip the duplicate copies of same node
vis[u] = 1;
for(auto &[v, w] : adj[u]) {
if(vis[v]) continue;
if(d[v] > d[u] + w) { // if can improve distance to node v from source
d[v] = d[u] + w;
Q.push({d[v], v});
// we dont mark visited here, because one node CAN
// be pushed into the PQ multiple times
}
}
}
}
Split node trick: Problem, Discussion
2nd shortest path: Discussion
Count the number of shortest paths: See here, Q3 in Challenge Questions