Hello Codeforces, this is my first blog and here I have given my solution of the complete CSES Graph Algorithms section. This is the github repo where I have pushed all the cpp files:
Counting Rooms
Thinking
used simple bfs in a grid
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
bool inrange(ll x, ll y, ll n, ll m)
{
if (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)))
return true;
return false;
}
int main()
{
ll n, m;
cin >> n >> m;
vector<string> v(n);
vector<vector<ll>> vis(n, vector<ll>(m));
for (auto &i : v)
{
cin >> i;
}
ll cnt = 0;
queue<pair<ll, ll>> q;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == '#')
continue;
if (vis[i][j] == 1)
continue;
q.push({i, j});
vis[i][j] = 1;
cnt++;
while (q.size() > 0)
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if ((inrange(nx, ny, n, m) && v[nx][ny] != '#') && vis[nx][ny] == 0)
{
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
}
cout << cnt;
}
Labyrinth
Thinking
used simple bfs and stored parent for path
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool inrange(ll x, ll y, ll n, ll m)
{
return (((0 <= x) && (x < n)) && ((0 <= y) && (y < m)));
}
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
pair<ll, ll> st;
pair<ll, ll> endd;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
st = {i, j};
}
if (v[i][j] == 'B')
{
endd = {i, j};
}
}
}
vector<vector<pair<ll, ll>>> prev(n, vector<pair<ll, ll>>(m, {-1, -1}));
vector<vector<ll>> vis(n, vector<ll>(m, 0));
vis[st.first][st.second] = 1;
queue<pair<ll, ll>> q;
q.push(st);
while (q.size())
{
ll x = q.front().first;
ll y = q.front().second;
q.pop();
for (ll j = 0; j < 4; j++)
{
ll nx = x + dx[j];
ll ny = y + dy[j];
if (!(inrange(nx, ny, n, m)))
continue;
if ((v[nx][ny] != '#') && (vis[nx][ny] == 0))
{
prev[nx][ny] = {x, y};
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
if (vis[endd.first][endd.second] == 0)
{
cout << "NO\n";
return 0;
}
vector<pair<ll, ll>> res;
// res.push_back(endd);
pair<ll, ll> curr = endd;
while (curr != st)
{
res.push_back(curr);
curr = {prev[curr.first][curr.second]};
}
res.push_back(st);
reverse(res.begin(), res.end());
// for(auto i: res)
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
cout << "YES\n";
cout << res.size() - 1 << "\n";
string direc = "";
for (ll i = 0; i < (ll)(res.size() - 1); i++)
{
if ((((res[i].first) + 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'D';
}
else if ((((res[i].first)) == (res[i + 1].first)) && ((((res[i].second + 1)) == (res[i + 1].second))))
{
direc += 'R';
}
else if ((((res[i].first) - 1) == (res[i + 1].first)) && ((((res[i].second)) == (res[i + 1].second))))
{
direc += 'U';
}
else
{
direc += 'L';
}
}
cout << direc << "\n";
}
Building Roads
Thinking
do bfs and store the starting vertex of each bfs traversal
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> v(n);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
x--;
y--;
v[x].push_back(y);
v[y].push_back(x);
}
vector<ll> vis(n, 0);
vector<ll> heads;
for (ll i = 0; i < n; i++)
{
if (vis[i] == 1)
continue;
heads.push_back(i);
queue<ll> q;
q.push(i);
vis[i] = 1;
while (q.size())
{
ll curr = q.front();
q.pop();
for (auto child : v[curr])
{
if (vis[child] == 1)
continue;
vis[child] = 1;
q.push(child);
}
}
}
// for(auto i: heads)
// {
// cout<<i<<" ";
// }
cout << heads.size() - 1 << "\n";
for (ll i = 0; i < ((ll)(heads.size() - 1)); i++)
{
cout << heads[i] + 1 << " " << heads[i + 1] + 1 << "\n";
}
}
}
Message Route
Thinking
do bfs and store parent
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> v(n);
while (m--)
{
ll x, y;
cin >> x >> y;
x--;
y--;
v[x].push_back(y);
v[y].push_back(x);
}
vector<ll> vis(n, 0);
queue<ll> q;
q.push(0);
vis[0] = 1;
vector<ll> prev(n, -1);
while (q.size())
{
ll curr = q.front();
q.pop();
for (auto child : v[curr])
{
if (vis[child] == 1)
continue;
q.push(child);
vis[child] = 1;
prev[child] = curr;
}
}
if (vis[n - 1] == 0)
{
cout << "IMPOSSIBLE\n";
continue;
}
vector<ll> res;
ll cur = n - 1;
// res.push_back();
while (cur != 0)
{
res.push_back(cur);
cur = prev[cur];
}
res.push_back(cur);
reverse(res.begin(), res.end());
cout << res.size() << "\n";
for (auto i : res)
cout << i + 1 << " ";
}
}
Building Teams
Thinking
check if the graph can be divided into a bipartite graph using bfs.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<vector<ll>> adj(100001);
vector<ll> vis(100001, 0);
vector<ll> team(100001, 0);
bool dfs(ll node, ll ct)
{
vis[node] = 1;
team[node] = ct;
for (auto &i : adj[node])
{
if (team[i] == 0)
{
bool temp = dfs(i, 3 - ct);
if (temp == false)
return false;
}
else if (team[i] == ct)
{
return false;
}
}
return true;
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
while (m--)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
bool ans = true;
for (ll i = 1; i <= n; i++)
{
if (vis[i])
continue;
ll res = dfs(i, 1);
if (!res)
{
ans = false;
break;
}
}
if (ans)
{
for (ll i = 1; i <= n; i++)
cout << team[i] << " ";
}
else
cout << "IMPOSSIBLE\n";
}
}
Round Trip
Thinking
use graph coloring to detect and print cycle by storing parent for each node.. as soon as cycle is detected ,.. print cycle and end program
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll paret[100005];
ll colour[100005];
ll vis[100005];
vector<vector<ll>> adj(100005);
bool dfs(int node, int parent)
{
vis[node] = 1;
paret[node] = parent;
colour[node] = 1;
for (auto child : adj[node])
{
if (child != parent && colour[child] == 1)
{
vector<ll> res;
ll x = node;
while (x != child)
{
res.push_back(x);
x = paret[x];
}
res.push_back(x);
// if(res[0]==res[res.size()-1])
// res.pop_back();
res.push_back(res[0]);
cout << res.size() << "\n";
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
else if (child != parent && colour[child] == 0)
{
bool temp = dfs(child, node);
if (temp == true)
{
vector<ll> res;
ll x = paret[child];
while (paret[x] != child)
{
res.push_back(x);
x = paret[x];
}
cout << res.size() << "\n";
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
}
}
colour[node] = 2;
return false;
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
while (m--)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 1)
{
continue;
}
// memset(colour,0,sizeof colour);
dfs(i, 0);
}
cout << "IMPOSSIBLE\n";
}
Monsters
Thinking
places where the monsters can reach before the person, can be considered to be as good as blocked,so first run a multisource bfs with all the monsters to find the time taken to reach all non blocked cells by the monsters then run a bfs using the persons position to find the time taken by the person to reach there finally if there is any boundary cell such that the person can reach it before the monsters,.. then print the path to it otherwise print impossible
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
bool issafe(ll x, ll y, ll n, ll m)
{
return ((0 <= x) && (x < n)) && ((0 <= y) && (y < m));
}
char pro(pair<ll, ll> a, pair<ll, ll> b)
{
if ((a.second + 1) == (b.second))
{
return 'R';
}
else if ((a.second - 1) == (b.second))
{
return 'L';
}
else if ((a.first - 1) == (b.first))
{
return 'U';
}
else
return 'D';
}
int main()
{
fastio;
ll t = 1;
// cin >> t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<string> v(n);
for (auto &i : v)
cin >> i;
queue<pair<ll, ll>> q;
vector<vector<ll>> dist(n, vector<ll>(m, LLONG_MAX));
vector<vector<bool>> vis(n, vector<bool>(m, false));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'M')
{
q.push({i, j});
dist[i][j] = 0;
vis[i][j] = true;
}
}
}
while (q.size() > 0)
{
auto z = q.front();
ll x = z.first;
ll y = z.second;
q.pop();
for (ll i = 0; i < 4; i++)
{
ll nx = x + dx[i];
ll ny = y + dy[i];
if ((issafe(nx, ny, n, m) && (v[nx][ny] != '#')) && (!vis[nx][ny]))
{
dist[nx][ny] = dist[x][y] + 1;
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
vector<vector<ll>> dista(n, vector<ll>(m, LLONG_MAX));
vector<vector<bool>> vista(n, vector<bool>(m, false));
queue<pair<ll, ll>> qa;
map<pair<ll, ll>, pair<ll, ll>> par;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (v[i][j] == 'A')
{
qa.push({i, j});
dista[i][j] = 0;
vista[i][j] = true;
par[{i, j}] = {i, j};
}
}
}
while (qa.size() > 0)
{
auto z = qa.front();
ll x = z.first;
ll y = z.second;
qa.pop();
for (ll i = 0; i < 4; i++)
{
ll nx = x + dx[i];
ll ny = y + dy[i];
if (((issafe(nx, ny, n, m) && v[nx][ny] != '#')) && (!vista[nx][ny]))
{
dista[nx][ny] = dista[x][y] + 1;
vista[nx][ny] = true;
qa.push({nx, ny});
par[{nx, ny}] = {x, y};
}
}
}
vector<pair<ll, ll>> res;
bool f = true;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
if (((i == 0) || (j == 0)) || ((i == n - 1) || (j == m - 1)))
{
if (dista[i][j] < dist[i][j])
{
pair<ll, ll> z = {i, j};
while (par[z] != z)
{
res.push_back(z);
z = par[z];
}
res.push_back(z);
f = false;
break;
}
}
}
if (!f)
{
break;
}
}
// for (auto &i : res)
// {
// cout << i.first << " " << i.second << "\n";
// }
if (!f)
{
cout << "YES\n";
ll x = res.size();
cout << x - 1 << "\n";
reverse(res.begin(), res.end());
for (ll i = 0; i < x - 1; i++)
{
char ch = pro(res[i], res[i + 1]);
cout << ch;
}
}
else
{
cout << "NO\n";
}
// for (auto &i : dist)
// {
// for (auto &j : i)
// {
// cout << j << " ";
// }
// cout << "\n";
// }
}
}
Shortest Routes I
Thinking
simple djikstra
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin/>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
vector<ll> dist(n + 1, LLONG_MAX);
dist[1] = 0;
while (m--)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, 1});
while (pq.size())
{
ll distance = pq.top().first;
ll node = pq.top().second;
pq.pop();
if (distance > dist[node])
continue;
for (auto &child : adj[node])
{
if (dist[child.first] > distance + (child.second))
{
dist[child.first] = distance + (child.second);
pq.push({distance + (child.second), child.first});
}
}
}
for (ll i = 1; i <= n; i++)
cout << dist[i] << " ";
}
}
Shortest Routes II
Thinking
simple Floyd Warshall
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin/>>t;
while (t--)
{
ll n, m, q;
cin >> n >> m >> q;
vector<vector<pair<ll, ll>>> adj(n + 1);
// vector<ll> dist(n+1,LLONG_MAX);
// dist[1] = 0;
vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, LLONG_MAX));
while (m--)
{
ll u, v, w;
cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
for (ll i = 1; i <= n; i++)
dist[i][i] = 0;
for (ll k = 1; k <= n; k++)
{
for (ll i = 1; i <= n; i++)
{
for (ll j = 1; j <= n; j++)
{
if ((dist[i][k] != LLONG_MAX) && (dist[k][j] != LLONG_MAX))
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
while (q--)
{
ll x, y;
cin >> x >> y;
cout << ((dist[x][y] == LLONG_MAX) ? -1 : dist[x][y]) << "\n";
}
// for(ll i=1;i<=n;i++)
// cout<<dist[i]<<" ";
}
}
High Score
Thinking
negate the edge weights and use bellman ford to get the minimum negative score ,.. i.e. the max score in positive numbers
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<ll> vis(2501, 0);
void dfs(ll node, ll parent, vector<ll> &reachable, vector<vector<ll>> &adjrev)
{
if (vis[node] == 1)
{
return;
}
else
{
reachable.push_back(node);
vis[node] = 1;
for (auto &i : adjrev[node])
{
if (i == parent)
continue;
dfs(i, node, reachable, adjrev);
}
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
vector<pair<pair<ll, ll>, ll>> edges;
for (ll i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
edges.push_back({{u, v}, -w});
adj[u].push_back({v, -w});
}
vector<ll> dist(n + 1, LLONG_MAX);
dist[1] = 0;
for (ll i = 1; i <= n; i++)
{
for (ll j = 0; j < m; j++)
{
ll u = edges[j].first.first;
ll v = edges[j].first.second;
ll w = edges[j].second;
if (dist[u] != LLONG_MAX)
{
dist[v] = min(dist[v], dist[u] + w);
}
}
}
// bool f = true;
ll x = dist[n];
set<ll> temp;
for (ll j = 0; j < m; j++)
{
ll u = edges[j].first.first;
ll v = edges[j].first.second;
ll w = edges[j].second;
if (dist[u] != LLONG_MAX)
{
ll x = dist[v];
dist[v] = min(dist[v], dist[u] + w);
if (x != dist[v])
temp.insert(v);
}
}
for (auto &i : edges)
{
swap(i.first.first, i.first.second);
}
vector<vector<ll>> adjrev(n + 1);
for (ll i = 0; i < m; i++)
{
ll u = edges[i].first.first;
ll v = edges[i].first.second;
adjrev[u].push_back(v);
}
vector<ll> reachable;
dfs(n, -1, reachable, adjrev);
bool f = true;
for (auto &i : reachable)
{
if (temp.find(i) != temp.end())
{
f = false;
break;
}
}
// if (x != dist[n])
// {
// f = false;
// }
if (f)
cout << -dist[n] << "\n";
else
cout << "-1\n";
}
Flight Discount
Thinking
use state djikstra What is state djikstra you might ask:
State djikstra
This is an extension of djikstra algorithm in which you process each node as a state,.. i.e. you maintain a variable to denote whether the discount has been used till now or not,.. and you push it into the priority queue along with the node number,.. For further clarification,.. see the code.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
// adj[v].push_back({u, w});
}
priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;
vector<vector<ll>> dis(n + 1, vector<ll>(2, LLONG_MAX));
dis[1][0] = 0;
dis[1][1] = 0;
pq.push({0, 1, 1});
while (pq.size() > 0)
{
auto z = pq.top();
pq.pop();
ll dist = z[0];
ll node = z[1];
ll available = z[2];
if (dis[node][available] < dist)
continue;
for (auto &ch : adj[node])
{
if (available == 1)
{
if (dis[ch.first][1] > (dist + ch.second))
{
dis[ch.first][1] = dist + ch.second;
pq.push({dis[ch.first][1], ch.first, 1});
}
if (dis[ch.first][0] > (dist + (ch.second) / 2))
{
dis[ch.first][0] = (dist + (ch.second) / 2);
pq.push({dis[ch.first][0], ch.first, 0});
}
}
else
{
if (dis[ch.first][0] > (dist + (ch.second)))
{
dis[ch.first][0] = (dist + (ch.second));
pq.push({dis[ch.first][0], ch.first, 0});
}
}
}
}
cout << min(dis[n][0], dis[n][1]) << "\n";
}
Cycle Finding
Thinking
use bellman ford to detect the presence of a negative cycle,.. Now, to print it,.. run bellman ford again(keep track of parent of nodes),... now,.. take any node whose value gets updated and keep on visiting its parent until the node itself is found,.. and u have found ur cycle .
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
vector<vector<ll>> edges;
for (ll i = 0; i < m; i++)
{
ll x, y, w;
cin >> x >> y >> w;
adj[x].push_back({y, w});
edges.push_back({x, y, w});
}
vector<ll> dist(n + 1, 3);
dist[1] = 0;
for (ll i = 0; i < n; i++)
{
for (auto &edge : edges)
{
ll u = edge[0];
ll v = edge[1];
ll w = edge[2];
dist[v] = min(dist[v], dist[u] + w);
}
}
bool f = true;
vector<ll> par(n + 1, -1);
for (ll i = 0; i < n; i++)
{
for (auto &edge : edges)
{
ll u = edge[0];
ll v = edge[1];
ll w = edge[2];
ll z = dist[v];
dist[v] = min(dist[v], dist[u] + w);
if (dist[v] != z)
{
f = false;
par[v] = u;
}
// }
}
}
if (f)
{
cout << "NO\n";
}
else
{
ll x = 0;
for (ll i = 1; i <= n; i++)
{
if (par[i] != -1)
{
x = i;
break;
}
}
vector<ll> cycle;
unordered_set<ll> st;
while (st.find(x) == st.end())
{
cycle.push_back(x);
st.insert(x);
x = par[x];
}
cycle.push_back(x);
reverse(cycle.begin(), cycle.end());
cout << "YES\n";
unordered_set<ll> final;
for (auto &i : cycle)
{
cout << i << " ";
if (final.find(i) != final.end())
{
break;
}
final.insert(i);
}
}
}
Flight Routes
Thinking
Do djikstra,.. and keep track of all the distances...in a max heap.. if the size of the maxheap for the nth node is greater than n,.. then pop the largest element and insert the current distance if it is smaller than the top of the max heap
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
int n, m, k;
cin >> n >> m >> k;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
priority_queue<ll> bes[n + 1];
vector<pair<ll, ll>> adj[n + 1];
for (ll i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
}
bes[1].push(0);
pq.push({0, 1});
while (pq.size() > 0)
{
auto a = pq.top();
pq.pop();
if (a.first > bes[a.second].top())
continue;
for (auto &i : adj[a.second])
{
ll tmp = a.first + i.second;
if (bes[i.first].size() < k)
{
bes[i.first].push(tmp);
pq.push({tmp, i.first});
}
else if (tmp < bes[i.first].top())
{
bes[i.first].pop();
bes[i.first].push(tmp);
pq.push({tmp, i.first});
}
}
}
vector<ll> ans;
while (bes[n].size() > 0)
{
ans.push_back(bes[n].top());
bes[n].pop();
}
reverse(ans.begin(), ans.end());
for (auto a : ans)
cout << a << " ";
}
Round Trip II
Thinking
same as round trip,..except here the graph is directed
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll paret[100005];
ll colour[100005];
ll vis[100005];
vector<vector<ll>> adj(100005);
bool dfs(int node, int parent)
{
vis[node] = 1;
paret[node] = parent;
colour[node] = 1;
for (auto child : adj[node])
{
if (colour[child] == 1)
{
vector<ll> res;
ll x = node;
while (x != child)
{
res.push_back(x);
x = paret[x];
}
res.push_back(x);
// if(res[0]==res[res.size()-1])
// res.pop_back();
res.push_back(res[0]);
cout << res.size() << "\n";
reverse(res.begin(), res.end());
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
else if (colour[child] == 0)
{
bool temp = dfs(child, node);
if (temp == true)
{
vector<ll> res;
ll x = paret[child];
while (paret[x] != child)
{
res.push_back(x);
x = paret[x];
}
cout << res.size() << "\n";
reverse(res.begin(), res.end());
for (auto x : res)
cout << x << " ";
exit(0);
return true;
}
}
}
colour[node] = 2;
return false;
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
while (m--)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
// adj[y].push_back(x);
}
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 1)
{
continue;
}
// memset(colour,0,sizeof colour);
dfs(i, 0);
}
cout << "IMPOSSIBLE\n";
}
Course Schedule
Thinking
topological sort using vertex removal algorithm
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool comp(const pair<ll, ld> &a, const pair<ll, ld> &b)
{
}
int main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<ll> in_degree(n + 1, 0);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
in_degree[y]++;
}
queue<ll> q;
for (ll i = 1; i < n + 1; i++)
{
if (in_degree[i] == 0)
{
q.push(i);
}
}
vector<ll> topo_sort;
while (q.size())
{
ll x = q.front();
q.pop();
topo_sort.push_back(x);
bool f = true;
for (auto &i : adj[x])
{
in_degree[i]--;
if (in_degree[i] == 0)
{
q.push(i);
f = false;
}
}
// if(f)
// {
// cout<<"IMPOSSIBLE\n";
// exit(0);
// }
}
if (topo_sort.size() == n)
{
for (auto i : topo_sort)
{
cout << i << " ";
}
}
else
{
cout << "IMPOSSIBLE\n";
}
}
}
Longest Flight Route
Thinking
it is given that the graph is a DAG(Directed acyclic graph),.. so we can use DP
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<ll> dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<vector<ll>> &dp)
{
if (node == dest)
{
return {1, -1, 1};
}
if (!(((dp[node][0] == -1) && (dp[node][1] == -1)) && (dp[node][2] == -1)))
{
return dp[node];
}
ll f = 0;
ll dist = 0;
ll nextcity = -1;
for (auto &i : adj[node])
{
vector<ll> z = dfs(i, dest, adj, dp);
if (z[2] == 1)
{
f = 1;
if (dist < z[0])
{
dist = z[0];
nextcity = i;
}
}
}
return (dp[node] = {dist + 1, nextcity, f});
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
}
vector<vector<ll>> dp(n + 1, vector<ll>(3, -1));
ll x = 1;
if (dfs(1, n, adj, dp)[2] != 1)
{
cout << "IMPOSSIBLE\n";
}
else
{
cout << dfs(1, n, adj, dp)[0] << "\n";
ll x = 1;
while (dfs(x, n, adj, dp)[1] != -1)
{
cout << x << " ";
x = dfs(x, n, adj, dp)[1];
}
cout << x << "\n";
}
}
Game Routes
Thinking
again its a DAG,.. so we use dp
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll mod = (ll)(1e9 + 7);
pair<ll, ll> dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<pair<ll, ll>> &dp) // ways,possibel
{
if (node == dest)
{
return {1, 1};
}
if (!((dp[node].first == -1) && (dp[node].second == -1)))
{
return dp[node];
}
ll ways = 0;
ll f = 0;
for (auto &i : adj[node])
{
auto z = dfs(i, dest, adj, dp);
if (z.second == 1)
{
f = 1;
ways += z.first;
ways %= mod;
}
}
return (dp[node] = {ways, f});
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
}
vector<pair<ll, ll>> dp(n + 1, {-1, -1});
auto z = dfs(1, n, adj, dp);
cout << z.first << "\n";
}
Investigation
Thinking
state djikstra for each node,.. maintain the given four states: dist,ways,minc,maxc
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll mod = (ll)(1e9 + 7);
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> adj(n + 1);
for (ll i = 0; i < m; i++)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
// vector<pair<ll, ll>> dist(n + 1, {LLONG_MAX, 0}); // dist,ways
vector<ll> dist(n + 1, LLONG_MAX);
vector<ll> ways(n + 1, 0);
vector<ll> minc(n + 1, 0);
vector<ll> maxc(n + 1, 0);
dist[1] = 0;
ways[1] = 1;
minc[1] = 1;
maxc[1] = 1;
pq.push({0, 1});
while (pq.size() > 0)
{
auto z = pq.top();
pq.pop();
ll u = z.second;
ll w = z.first;
if (dist[u] < w)
{
continue;
}
for (auto &i : adj[u])
{
ll v = i.first;
ll weight = i.second;
if (dist[v] > w + weight)
{
dist[v] = w + weight;
ways[v] = ways[u];
minc[v] = minc[u] + 1;
maxc[v] = maxc[u] + 1;
pq.push({dist[v], v});
}
else if (dist[v] == (w + weight))
{
// dist[v] = w + weight;
ways[v] += ways[u];
ways[v] %= mod;
minc[v] = min(minc[v], minc[u] + 1);
maxc[v] = max(maxc[v], maxc[u] + 1);
}
}
}
cout << dist[n] << " " << ways[n] << " " << minc[n] - 1 << " " << maxc[n] - 1 << "\n";
}
Planet Queries I
Thinking
use binary jumping i.e. for each node calculate findpar(x,k).. i.e. the 2^k th successor of node x. Now if we need to find the dth successor of the xth node, represent d as the sum of powers of 2. This is similar to binary lifting used to find the kth ancestor of a node in a tree.
Code
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll n, q;
// vector<vector<ll>> dp(2e5 + 1, vector<ll>(30, -1));
ll dp[200001][30];
ll findpar(ll node, ll k)
{
ll x = node;
for (ll i = 0; i < 30; i++)
{
if (k & (1ll << i))
{
// x = f(x, i, dp, par);
x = dp[x][i];
}
}
return x;
}
int main()
{
fastio;
cin >> n >> q;
for (ll i = 1; i <= n; i++)
{
cin >> dp[i][0];
}
for (ll i = 1; i < 30; i++)
{
for (ll j = 1; j <= n; j++)
{
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
while (q--)
{
ll a, b;
cin >> a >> b;
cout << findpar(a, b) << "\n";
}
}
Planet Queries II
Thinking
This is a successor graph,.. so it can be divided into components having a cycle and a paths pointing to the cycle so if the nodes belong to the same cycle,.. then the distance is (dfs number(v)-dfs number(u)+cyclelength)%cyclelength else if both are not part of any cycle,.. then if we jump from u by (dfs number(v)-dfs number(v)), and we reach v,.. then the answer is jump else its -1 now if one node is in a cycle and the other isnt then the one outside the cycle,.. we find the nearest cycle node to it using binary jumping and binary search let this closest cycle node be called interm(as in intermediate node) now dist = distance between u and interm + distance between interm and y(can be found using (dfs number(y)-dfs number(interm)+cyclelength)%cyclelength.. as shown int the above case)
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
void addno(ll i, unordered_set<ll> &done, vector<ll> &nextnode, vector<ll> &no)
{
if (done.find(i) != done.end())
return;
addno(nextnode[i], done, nextnode, no);
done.insert(i);
no[i] = no[nextnode[i]] - 1;
}
ll dp[200005][30];
ll findpar(ll node, ll k)
{
ll x = node;
for (ll i = 0; i < 30; i++)
{
if (k & (1ll << i))
{
// x = f(x, i, dp, par);
x = dp[x][i];
}
}
return x;
}
int main()
{
fastio;
ll n, q;
cin >> n >> q;
vector<ll> nextnode(n + 1);
for (ll i = 1; i <= n; i++)
{
cin >> nextnode[i];
dp[i][0] = nextnode[i];
}
vector<ll> vis(n + 1, 0);
for (ll i = 1; i < 30; i++)
{
for (ll j = 1; j <= n; j++)
{
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
// vector<ll> answer(n + 1, -1);
vector<vector<ll>> cycles;
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
unordered_set<ll> tempset;
vector<ll> tempvec;
ll x = i;
bool flag = true;
while (tempset.find(x) == tempset.end())
{
tempset.insert(x);
tempvec.push_back(x);
if (vis[x])
{
flag = false;
break;
}
x = nextnode[x];
}
if (!flag)
{
for (auto &i : tempvec)
vis[i] = 1;
continue;
}
ll z = find(tempvec.begin(), tempvec.end(), x) - tempvec.begin();
ll m = tempvec.size();
vector<ll> cycle;
for (ll i = z; i < m; i++)
{
vis[tempvec[i]] = 1;
cycle.push_back(tempvec[i]);
}
for (ll i = z - 1; i >= 0; i--)
{
vis[tempvec[i]] = 1;
}
cycles.push_back(cycle);
}
}
vector<ll> no(n + 1, -1);
unordered_set<ll> done;
vector<ll> cycleidx(n + 1, -1);
ll idx = 0;
for (auto &i : cycles)
{
ll c = 0;
for (auto &j : i)
{
no[j] = c++;
cycleidx[j] = idx;
done.insert(j);
}
idx++;
}
for (ll i = 1; i <= n; i++)
{
addno(i, done, nextnode, no);
}
// for (ll i = 1; i <= n; i++)
// cout << cycleidx[i] << " " << no[i] << "\n";
while (q--)
{
ll x, y;
cin >> x >> y;
if ((cycleidx[x] == cycleidx[y]) && ((cycleidx[x] != -1) && (cycleidx[y] != -1)))
{
ll b = cycles[cycleidx[x]].size();
cout << ((no[y] - no[x] + b) % b) << "\n";
}
else if ((cycleidx[x] == -1) || (cycleidx[y] == -1))
{
if ((cycleidx[x] == -1) && (cycleidx[y] == -1))
{
if (no[x] > no[y])
cout << "-1\n";
else
{
ll jump = no[y] - no[x];
if (findpar(x, jump) == y)
cout << jump << "\n";
else
cout << "-1\n";
}
}
else
{
// if (no[x] > no[y])
// {
if ((cycleidx[x] != -1) && (cycleidx[y] == -1))
cout << "-1\n";
else
{
ll lo = 0;
ll hi = n;
ll ans = -1;
while (lo <= hi)
{
ll mid = (lo + hi) / 2;
if (cycleidx[findpar(x, mid)] != -1)
{
ans = mid;
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
ll interm = findpar(x, ans);
if (cycleidx[interm] == cycleidx[y])
{
ll h = cycles[cycleidx[y]].size();
cout << ((no[interm] - no[x]) + ((no[y] - no[interm] + h) % h)) << "\n";
}
else
{
cout << "-1\n";
}
}
}
}
else
{
cout << "-1\n";
}
}
}
Planet Cycles
Thinking
this is again a successor graph,.. so we divide it into components having a cycle and paths pointing to the cycles,.. so we do dfs,.. and keep track of the dfs numbers for each node in the cycle,.. the answer is the cycle length.. for other nodes,.. let the node be x,..ans[x] = ans[nextnode[x]]+1
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n;
cin >> n;
vector<ll> nextnode(n + 1);
for (ll i = 1; i <= n + 1; i++)
{
cin >> nextnode[i];
}
vector<ll> vis(n + 1, 0);
vector<ll> answer(n + 1, -1);
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
unordered_set<ll> tempset;
vector<ll> tempvec;
ll x = i;
bool flag = true;
while (tempset.find(x) == tempset.end())
{
tempset.insert(x);
tempvec.push_back(x);
if (vis[x])
{
flag = false;
break;
}
x = nextnode[x];
}
ll z = find(tempvec.begin(), tempvec.end(), x) - tempvec.begin();
ll m = tempvec.size();
for (ll i = z; i < m; i++)
{
vis[tempvec[i]] = 1;
if (answer[tempvec[i]] == -1)
answer[tempvec[i]] = m - z;
}
for (ll i = z - 1; i >= 0; i--)
{
vis[tempvec[i]] = 1;
if (answer[tempvec[i]] == -1)
answer[tempvec[i]] = answer[tempvec[i + 1]] + 1;
}
}
}
for (ll i = 1; i <= n; i++)
cout << answer[i] << " ";
}
Road Reparation
Thinking
simple MST finding,.. I have implemented using kruskals algo
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector<ll> ranq(100001);
vector<ll> par(100001);
void make_set(ll n)
{
for (ll i = 1; i <= n; i++)
{
ranq[i] = 1;
par[i] = i;
}
}
ll find_set(ll x)
{
if (par[x] == x)
{
return x;
}
par[x] = find_set(par[x]);
return par[x];
}
void union_set(ll a, ll b)
{
ll x = find_set(a);
ll y = find_set(b);
if (x == y)
return;
if (ranq[x] > ranq[y])
{
par[y] = x;
ranq[x] += ranq[y];
}
else
{
par[x] = y;
ranq[y] += ranq[x];
}
}
int32_t main()
{
fastio;
ll t = 1;
// cin>>t;
while (t--)
{
ll n, m;
cin >> n >> m;
make_set(n);
vector<pair<ll, pair<ll, ll>>> v;
while (m--)
{
ll a, b, c;
cin >> a >> b >> c;
v.push_back({c, {a, b}});
}
sort(v.begin(), v.end());
m = v.size();
ll cost = 0;
for (ll i = 0; i < m; i++)
{
ll x = v[i].second.first;
ll y = v[i].second.second;
ll w = v[i].first;
if (find_set(x) != find_set(y))
{
cost += w;
union_set(x, y);
}
}
if (ranq[find_set(1)] == n)
{
cout << cost << "\n";
}
else
{
cout << "IMPOSSIBLE\n";
}
}
}
Road Construction
Thinking
we use dsu,.. while merging two nodes,if their parents were same,.. we return false,.. otherwise return true hence if two nodes were merged whose parents were different,.. then we can see that the number of components decreases otherwise if theri parents are same,.. it remains unchanged
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll maxcomp = 1;
vector<ll> ranq(100001);
vector<ll> par(100001);
void make_set(ll n)
{
for (ll i = 1; i <= n; i++)
{
ranq[i] = 1;
par[i] = i;
}
}
ll find_set(ll x)
{
if (x == par[x])
return x;
par[x] = find_set(par[x]);
return par[x];
}
bool union_set(ll a, ll b)
{
ll x = find_set(a);
ll y = find_set(b);
if (x == y)
return false;
if (ranq[x] > ranq[y])
{
par[y] = x;
ranq[x] += ranq[y];
if (ranq[x] > maxcomp)
{
maxcomp = ranq[x];
}
return true;
}
else
{
par[x] = y;
ranq[y] += ranq[x];
if (ranq[y] > maxcomp)
{
maxcomp = ranq[y];
}
return true;
}
}
int32_t main()
{
fastio;
ll t = 1;
while (t--)
{
ll n, m;
cin >> n >> m;
make_set(n);
ll nocomp = n;
while (m--)
{
ll x, y;
cin >> x >> y;
bool res = union_set(x, y);
if (res)
{
nocomp--;
}
cout << nocomp << " " << maxcomp << "\n";
}
}
}
Flight Routes Check
Thinking
the question reduces itself to the simple problem of checking if the entire graph is a single stringly connected component or not we apply kosaraju's algorithm to find sccs for each scc ,.. we store the head node i.e. while doing the second dfs in the decreasing order of finish times if there are 2 or more sccs,.. we print head nodes of the first 2 SCCs
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &finish, ll &timer, vector<ll> &vis)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
finish[node] = timer++;
}
void dfs2(ll node, vector<ll> &vis, vector<vector<ll>> &adj)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs2(i, vis, adj);
}
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<vector<ll>> adjt(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adjt[y].push_back(x);
}
vector<ll> finish(n + 1, -1);
vector<ll> vis(n + 1, 0);
ll timer = 0;
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
vector<ll> ord(n);
for (ll i = 0; i < n; i++)
{
ord[i] = i + 1;
}
sort(ord.begin(), ord.end(), [&](ll a, ll b)
{ return (finish[a] > finish[b]); });
vis.clear();
vis.resize(n + 1, 0);
ll cnt = 0;
vector<ll> nodes;
for (ll i = 0; i < n; i++)
{
if (vis[ord[i]] == 0)
{
nodes.push_back(ord[i]);
cnt++;
dfs2(ord[i], vis, adjt);
}
}
if (cnt == 1)
{
cout << "YES\n";
}
else
{
cout << "NO\n";
cout << nodes[1] << " " << nodes[0] << "\n";
}
}
Planets and Kingdoms
Thinking
we perform kosaraju's algorithm and find the scc to which each planet belongs to,.. while performing the second dfs,.. we also mark the planets with the current position of the kingdom,.. which is denoted in the above code by the variable c declared in line 76
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &finish, ll &timer, vector<ll> &vis)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
finish[node] = timer++;
}
void dfs2(ll node, vector<ll> &vis, vector<vector<ll>> &adj, ll king, vector<ll> &kingdom)
{
vis[node] = 1;
kingdom[node] = king;
for (auto &i : adj[node])
{
if (vis[i] == 0)
{
dfs2(i, vis, adj, king, kingdom);
}
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<vector<ll>> adjt(n + 1);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
adjt[y].push_back(x);
}
vector<ll> finish(n + 1, -1);
vector<ll> vis(n + 1, 0);
ll timer = 0;
for (ll i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
dfs(i, adj, finish, timer, vis);
}
}
vector<ll> ord(n);
for (ll i = 0; i < n; i++)
{
ord[i] = i + 1;
}
sort(ord.begin(), ord.end(), [&](ll a, ll b)
{ return (finish[a] > finish[b]); });
vis.clear();
vis.resize(n + 1, 0);
ll cnt = 0;
vector<ll> nodes;
vector<ll> kingdom(n + 1, -1);
ll c = 0;
for (ll i = 0; i < n; i++)
{
if (vis[ord[i]] == 0)
{
c++;
dfs2(ord[i], vis, adjt, c, kingdom);
}
}
cout << c << "\n";
for (ll i = 1; i <= n; i++)
{
cout << kingdom[i] << " ";
}
}
Giant Pizza
Thinking
this is a classical problem of 2-SAT recommended reading material: https://cp-algorithms.com/graph/2SAT.html
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int tval[200005];
vector<int> adj[200005], adj2[200005];
vector<int> v;
bool vis[200005];
void dfs(int s)
{
if (vis[s])
return;
vis[s] = 1;
for (auto i : adj[s])
dfs(i);
v.push_back(s);
}
int k = 0;
int comp[200005];
void dfs2(int s)
{
if (vis[s])
return;
vis[s] = 1;
comp[s] = k;
for (auto i : adj2[s])
dfs2(i);
}
int main()
{
// fastio;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
char x, y;
int a, b;
cin >> x >> a >> y >> b;
if (x == '-')
a = 2 * m - a + 1;
if (y == '-')
b = 2 * m - b + 1;
adj[2 * m - a + 1].push_back(b);
adj[2 * m - b + 1].push_back(a);
adj2[a].push_back(2 * m - b + 1);
adj2[b].push_back(2 * m - a + 1);
}
for (int i = 1; i <= 2 * m; i++)
{
if (!vis[i])
dfs(i);
}
memset(vis, 0, sizeof vis);
reverse(v.begin(), v.end());
for (auto i : v)
{
int x = i;
if (!vis[x])
{
k++;
dfs2(x);
}
}
for (ll i = 1; i <= m; i++)
{
if (comp[i] == comp[2 * m - i + 1])
{
cout << "IMPOSSIBLE\n";
return 0;
}
tval[i] = (comp[i] > comp[2 * m - i + 1]);
}
for (ll i = 1; i <= m; i++)
{
cout << ((tval[i]) ? '+' : '-') << " ";
}
}
Coin Collector
Thinking
we convert the given graph to a DAG,.. so the collector can visit one node os the DAG and collect all the coins which were originally present in the nodes which were converted to this node in the DAG to make it easier to implement SCC,.. I have made a class SCCmaker,.. u can go through the above code and save it as a template to easily implement conversion of a graph to a DAG in future :)
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
class SCCmaker
{
vector<vector<ll>> DAG;
vector<ll> info;
ll number_of_nodes;
void dfs(ll node, vector<vector<ll>> &adj, vector<ll> &vis, vector<ll> &order)
{
vis[node] = 1;
for (auto &i : adj[node])
{
if (vis[i] != 1)
{
dfs(i, adj, vis, order);
}
}
order.push_back(node);
}
void dfs2(ll node, vector<vector<ll>> &revadj, vector<ll> &temp, vector<ll> &vis)
{
vis[node] = 1;
temp.push_back(node);
for (auto &i : revadj[node])
{
if (vis[i] == 0)
{
dfs2(i, revadj, temp, vis);
}
}
}
public:
SCCmaker(vector<vector<ll>> &adj, vector<ll> &information, ll (*combine)(vector<ll> &temp, vector<ll> &information), vector<pair<ll, ll>> &edges, ll n)
{
vector<ll> order;
vector<ll> vis(n + 1, 0);
for (ll i = 1; i <= n; i++)
{
if (!vis[i])
dfs(i, adj, vis, order);
}
reverse(order.begin(), order.end());
vector<ll> vis2(n + 1, 0);
vector<vector<ll>> revadj(n + 1);
for (auto &i : edges)
{
revadj[i.second].push_back(i.first);
}
vector<ll> parentset(n + 1, 0);
ll c = 0;
for (auto &i : order)
{
if (!vis2[i])
{
vector<ll> temp;
dfs2(i, revadj, temp, vis2);
ll z = temp.size();
for (ll j = 0; j < z; j++)
{
parentset[temp[j]] = c;
}
ll sum = combine(temp, information);
info.push_back(sum);
c++;
}
}
DAG.resize(c);
number_of_nodes = c;
for (auto &i : edges)
{
if (parentset[i.first] != parentset[i.second])
{
DAG[parentset[i.first]].push_back(parentset[i.second]);
}
}
}
vector<vector<ll>> getDAG()
{
return DAG;
}
vector<ll> getinfo()
{
return info;
}
ll get_numberofnodes()
{
return number_of_nodes;
}
};
ll combine(vector<ll> &temp, vector<ll> &information)
{
ll sum = 0;
for (auto &i : temp)
{
sum += information[i - 1];
}
return sum;
}
ll solve(ll node, vector<vector<ll>> &DAG, vector<ll> &DAGinfo, vector<ll> &dp)
{
ll res = 0;
if (dp[node] != -1)
return dp[node];
for (auto &i : DAG[node])
{
res = max(res, solve(i, DAG, DAGinfo, dp));
}
return dp[node] = (res + DAGinfo[node]);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<ll> val(n);
for (auto &i : val)
{
cin >> i;
}
vector<vector<ll>> adj(n + 1);
vector<pair<ll, ll>> edges;
for (ll i = 1; i <= m; i++)
{
ll x, y;
cin >> x >> y;
edges.push_back({x, y});
adj[x].push_back(y);
}
SCCmaker sccmaker(adj, val, combine, edges, n);
ll DAGnodes = sccmaker.get_numberofnodes();
vector<vector<ll>> DAG = sccmaker.getDAG();
vector<ll> DAGinfo = sccmaker.getinfo();
vector<ll> dp(DAGnodes + 1, -1);
ll res = 0;
for (ll i = 0; i < DAGnodes; i++)
{
res = max(res, solve(i, DAG, DAGinfo, dp));
}
cout << res << "\n";
}
Mail Delivery
Thinking
recommended reading material: https://cp-algorithms.com/graph/euler_path.html I have implemented the algorithm as described in the article above
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<set<ll>> adj(n + 1);
vector<ll> deg(n + 1, 0);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].insert(y);
adj[y].insert(x);
deg[x]++;
deg[y]++;
}
stack<ll> st;
for (ll i = 1; i <= n; i++)
{
if (deg[i] % 2)
{
cout << "IMPOSSIBLE\n";
return 0;
}
}
vector<ll> path;
st.push(1);
while (st.size() > 0)
{
ll x = st.top();
if (deg[x] == 0)
{
st.pop();
path.push_back(x);
}
else
{
ll z = *(adj[x].begin());
adj[x].erase(z);
adj[z].erase(x);
deg[x]--;
deg[z]--;
st.push(z);
}
}
if (path.size() != (m + 1))
{
cout << "IMPOSSIBLE\n";
return 0;
}
for (auto &i : path)
{
cout << i << " ";
}
}
De Bruijn Sequence
Thinking
recommended reading material: https://cses.fi/book/book.pdf#page=188
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll n;
cin >> n;
if (n == 1)
{
cout << "01\n";
return 0;
}
ll N = (1 << (n - 1)) - 1;
vector<vector<ll>> adj(N + 1);
vector<ll> indeg(N + 1);
vector<ll> outdeg(N + 1);
for (ll i = 0; i <= N; i++)
{
ll num1 = (i * 2) % (1 << (max(0ll, (n - 1))));
ll num2 = ((i * 2) + 1) % (1 << (max(0ll, (n - 1))));
// cout << i << " " << num1 << " " << num2 << "\n";
adj[i].push_back(num1);
adj[i].push_back(num2);
outdeg[i] += 2;
indeg[num1]++;
indeg[num2]++;
}
vector<ll> path;
stack<ll> st;
st.push(0);
while (st.size() > 0)
{
ll x = st.top();
if ((indeg[x] == 0) && (outdeg[x] == 0))
{
path.push_back(x);
st.pop();
}
else
{
ll k = adj[x].back();
adj[x].pop_back();
indeg[k]--;
outdeg[x]--;
st.push(k);
}
}
reverse(path.begin(), path.end());
// for (auto &i : path)
// {
// cout << i << " ";
// }
string res = "";
for (ll i = 0; i < n - 1; i++)
{
res += '0';
}
ll m = path.size();
for (ll i = 0; i < m - 1; i++)
{
if (path[i + 1] == ((path[i] * 2) % (1 << (max(0ll, (n - 1))))))
{
res += '0';
}
else
{
res += '1';
}
}
// reverse(res.begin(), res.end());
cout << res << "\n";
// for (auto &i : path)
// {
// cout << i << " ";
// }
}
Teleporters Path
Thinking
this is a classic problem of finding the euler path recommended reading material: https://cp-algorithms.com/graph/euler_path.html I have implemented the algorithm as described in the article above
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
fastio;
ll t = 1;
// cin >> t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1);
vector<ll> indeg(n + 1, 0);
vector<ll> outdeg(n + 1, 0);
for (ll i = 0; i < m; i++)
{
ll x, y;
cin >> x >> y;
adj[x].push_back(y);
indeg[y]++;
outdeg[x]++;
}
for (ll i = 2; i < n; i++)
{
if (indeg[i] != outdeg[i])
{
cout << "IMPOSSIBLE\n";
return 0;
}
}
if (((outdeg[1] - indeg[1]) != 1) || ((outdeg[n] - indeg[n]) != -1))
{
cout << "IMPOSSIBLE\n";
return 0;
}
stack<ll> st;
st.push(1);
vector<ll> path;
while (st.size() > 0)
{
ll z = st.top();
if ((indeg[z] == 0) && (outdeg[z] == 0))
{
path.push_back(z);
st.pop();
}
else
{
ll m = adj[z].size();
st.push(adj[z][m - 1]);
adj[z].pop_back();
outdeg[z]--;
indeg[adj[z][m - 1]]--;
}
}
if (path.size() != (m + 1))
{
cout << "IMPOSSIBLE\n";
return 0;
}
reverse(path.begin(), path.end());
for (auto &i : path)
{
cout << i << " ";
}
}
}
Hamiltonian Flights
Thinking
it is the simple backtracking implementation of number of hamiltonian paths a mask variable is used in dfs to keep track of the nodes visited,.. if we reach the node n and the mask is 0(i.e. all the nodes are visited) then this counts as a valid path otherwise if the mask is not 0,..then it is not a valid path,.. and we return 0 we use a DP to memoize the results
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
#define MOD 1000000007
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
// ll mod = (ll)(1e9 + 7);
// vector<vector<int>> dp((1 << 21), vector<int>(21, -1));
ll dp[1 << 21][22];
vector<int> adj[22];
int n;
ll dfs(int mask, int node)
{
mask = mask ^ (1 << (node));
if ((mask == 0) && (node == (n - 1)))
{
return 1;
}
if (node == (n - 1))
{
return 0;
}
if (dp[mask][node] != -1)
{
return dp[mask][node];
}
// ll res = 0;
// dp[mask][node] = 0;
ll res = 0;
for (auto &i : adj[node])
{
if ((1ll << (i)) & mask)
{
res += dfs(mask, i);
res %= MOD;
}
}
return (dp[mask][node] = res);
}
int main()
{
fastio;
int m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
x--;
y--;
adj[x].push_back(y);
}
memset(dp, -1, sizeof(dp));
cout << dfs((1 << n) - 1, 0);
}
Knight's Tour
Thinking
here also we use backtracking,.. but we need to find only one solution.. so instead of randomly choosing the next square for the knight to move,.. we sort the available squares according to the number of squares available to go from them in a non increasing order. This allows us to always visit the square from which we have the maximum chance of having a next place to move the knight to and hence optimizes the solution PS: without this optimization,. the code will give tle
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
ll board[8][8];
bool issafe(int x, int y)
{
return (((0 <= x) && (x < 8)) && ((0 <= y) && (y < 8)));
}
int deg(ll x, ll y)
{
int s = 0;
for (ll i = 0; i < 8; i++)
{
ll nx = x + dx[i];
ll ny = y + dy[i];
if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] != -1))
s++;
}
return s;
}
bool dfs(int x, int y, int move)
{
board[x][y] = move;
if (move == 64)
{
return true;
}
vector<vector<int>> vec;
for (int i = 0; i < 8; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if ((((0 <= nx) && (nx < 8)) && ((0 <= ny) && (ny < 8))) && (board[nx][ny] == 0))
{
int d = deg(nx, ny);
vec.push_back({d, nx, ny});
}
}
sort(vec.begin(), vec.end());
for (auto &i : vec)
{
if (dfs(i[1], i[2], move + 1))
return true;
}
board[x][y] = 0;
return false;
}
int main()
{
fastio;
ll x, y;
cin >> y >> x;
x--;
y--;
memset(board, 0, sizeof(board));
bool res = dfs(x, y, 1);
for (auto &i : board)
{
for (auto &j : i)
{
cout << j << " ";
}
cout << "\n";
}
}
Download Speed
Thinking
this is a problem of finding the maximum flow in a graph this is solved by implementing the ford fulkerson algorithm recommended reading material: https://cses.fi/book/book.pdf#page=191 I personally recommend to use the scaling algorithm to find paths for the ford fulkerson algorithm as it is easier to implement scaling algorithm: https://cses.fi/book/book.pdf#page=195
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis)
{
vis[node] = 1;
if (node == dest)
{
path.push_back(node);
return true;
}
for (ll i = 1; i <= dest; i++)
{
if (adj[node][i] == -1)
continue;
if (vis[i])
continue;
if (adj[node][i] < threshhold)
{
continue;
}
if (dfs(i, dest, adj, path, threshhold, vis))
{
path.push_back(node);
return true;
}
}
return false;
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));
ll sum = 0;
for (ll i = 0; i < m; i++)
{
ll x, y, w;
cin >> x >> y >> w;
if (adj[x][y] == -1)
{
adj[x][y] = 0;
}
adj[x][y] += w;
adj[y][x] = 0;
sum += w;
}
ll ans = 0;
while (sum > 0)
{
vector<ll> path;
vector<ll> vis(n + 1, 0);
bool f = dfs(1, n, adj, path, sum, vis);
if (f == true)
{
reverse(path.begin(), path.end());
ll k = path.size();
ll minedgewt = LLONG_MAX;
for (ll i = 0; i < k - 1; i++)
{
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
}
ans += minedgewt;
for (ll i = 0; i < k - 1; i++)
{
adj[path[i]][path[i + 1]] -= minedgewt;
adj[path[i + 1]][path[i]] += minedgewt;
}
}
else
sum /= 2;
}
cout << ans << "\n";
}
Police Chase
Thinking
this is a problem of the finding the minimum cut this is implemented using the ford fulkerson algorithm it is strongly recommended to either solve or read the editorial of download speed problem proceeding recommended reading material: https://cses.fi/book/book.pdf#page=195
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)
{
vis[node] = 1;
if (node == dest)
{
path.push_back(node);
return true;
}
for (ll i = 1; i <= n; i++)
{
if (adj[node][i] == -1)
continue;
if (vis[i])
continue;
if (adj[node][i] < threshhold)
{
continue;
}
if (dfs(i, dest, adj, path, threshhold, vis, n))
{
path.push_back(node);
return true;
}
}
return false;
}
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)
{
visited[node] = 1;
left.push_back(node);
for (ll i = 1; i <= n; i++)
{
if (visited[i])
continue;
if (og[node][i] <= 0)
continue;
dfs2(i, og, left, visited, n);
}
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));
vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));
ll sum = 0;
for (ll i = 0; i < m; i++)
{
ll x, y;
ll w = 1;
cin >> x >> y;
og[x][y] = w;
og[y][x] = w;
if (adj[x][y] == -1)
{
adj[x][y] = 0;
adj[y][x] = 0;
}
adj[x][y] += w;
adj[y][x] += w;
sum += w;
}
ll ans = 0;
while (sum > 0)
{
vector<ll> path;
vector<ll> vis(n + 1, 0);
bool f = dfs(1, n, adj, path, sum, vis, n);
if (f == true)
{
reverse(path.begin(), path.end());
ll k = path.size();
ll minedgewt = LLONG_MAX;
for (ll i = 0; i < k - 1; i++)
{
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
}
ans += minedgewt;
for (ll i = 0; i < k - 1; i++)
{
adj[path[i]][path[i + 1]] -= minedgewt;
adj[path[i + 1]][path[i]] += minedgewt;
}
}
else
sum /= 2;
}
cout << ans << "\n";
vector<ll> left;
vector<ll> visited(n + 1, 0);
dfs2(1, adj, left, visited, n);
unordered_set<ll> st;
for (auto &i : left)
st.insert(i);
for (auto &i : left)
{
for (ll j = 1; j <= n; j++)
{
if (((og[i][j] == 1) && (adj[i][j] == 0)) && (st.find(j) == st.end()))
{
cout << i << " " << j << "\n";
}
}
}
}
School Dance
Thinking
this is a problem of finding the maximum matching recommended reading material: https://cses.fi/book/book.pdf#page=197 I have implemented this article in the above code
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)
{
vis[node] = 1;
if (node == dest)
{
path.push_back(node);
return true;
}
for (ll i = 0; i <= n; i++)
{
if (adj[node][i] == -1)
continue;
if (vis[i])
continue;
if (adj[node][i] < threshhold)
{
continue;
}
if (dfs(i, dest, adj, path, threshhold, vis, n))
{
path.push_back(node);
return true;
}
}
return false;
}
void dfs2(ll node, vector<vector<ll>> &og, vector<ll> &left, vector<ll> &visited, ll n)
{
visited[node] = 1;
left.push_back(node);
for (ll i = 0; i <= n; i++)
{
if (visited[i])
continue;
// if (og[node][i] == -1)
// continue;
// if (og[node][i] == 0)
// continue;
if (og[node][i] <= 0)
continue;
dfs2(i, og, left, visited, n);
}
}
int main()
{
fastio;
ll n, m, k;
cin >> n >> m >> k;
vector<vector<ll>> adj(n + m + 2, vector<ll>(n + m + 2, -1));
vector<vector<ll>> og(n + m + 2, vector<ll>(n + m + 2, -1));
ll sum = 0;
for (ll i = 0; i < k; i++)
{
ll x, y;
ll w = 1;
cin >> x >> y;
y += n;
// y += 500;
og[x][y] = w;
// og[y][x] = w;
// og[y][x] = w;
if (adj[x][y] == -1)
{
adj[x][y] = 0;
// adj[y][x] = 0;
}
adj[x][y] = w;
adj[y][x] = 0;
sum += w;
}
for (ll i = 1; i <= n; i++)
{
adj[0][i] = 1;
og[0][i] = 1;
}
for (ll i = n + 1; i <= n + m; i++)
{
adj[i][n + m + 1] = 1;
og[i][n + m + 1] = 1;
}
ll ans = 0;
while (sum > 0)
{
vector<ll> path;
vector<ll> vis(n + m + 2, 0);
bool f = dfs(0, n + m + 1, adj, path, sum, vis, n + m + 1);
if (f == true)
{
reverse(path.begin(), path.end());
ll z = path.size();
ll minedgewt = LLONG_MAX;
for (ll i = 0; i < z - 1; i++)
{
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
}
ans += minedgewt;
for (ll i = 0; i < z - 1; i++)
{
adj[path[i]][path[i + 1]] -= minedgewt;
adj[path[i + 1]][path[i]] += minedgewt;
}
}
else
sum /= 2;
}
// for (ll i = 0; i <= n + m + 1; i++)
// {
// for (ll j = 0; j <= n + m + 1; j++)
// {
// cout << adj[i][j] << " ";
// }
// cout << "\n";
// }
cout << ans << "\n";
vector<ll> left;
// vector<ll> visited(n + m + 2, 0);
// dfs2(0, adj, left, visited, n + m + 1);
for (ll i = 1; i <= n; i++)
{
left.push_back(i);
}
unordered_set<ll> st;
for (auto &i : left)
{
st.insert(i);
}
for (auto &i : left)
{
for (ll j = n + 1; j <= n + m; j++)
{
if (((og[i][j] == 1) && (adj[i][j] == 0)))
{
cout << i << " " << j - n << "\n";
}
}
}
}
Distinct Routes
Thinking
this is a problem of finding the maximum flow again read this: https://cses.fi/book/book.pdf#page=196 this article helps you to find the length of the path now to find the path.. we do this: start from vertex 1 go through all the edges,.. and check if there is an edge,.. whose reverse edge(that we artificially create in ford fulkerson algorithm) has a value,.. and this edge has value 0 this means that this edge is included in the max flow path we coninue this till we reach the end finally we print the answer. We maintain a set of pairs to make sure we don't consider an edge twice
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fr(i, n) for (ll i = 0; i < n; i++)
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool dfs(ll node, ll dest, vector<vector<ll>> &adj, vector<ll> &path, ll threshhold, vector<ll> &vis, ll n)
{
vis[node] = 1;
if (node == dest)
{
path.push_back(node);
return true;
}
for (ll i = 1; i <= n; i++)
{
if (adj[node][i] == -1)
continue;
if (vis[i])
continue;
if (adj[node][i] < threshhold)
{
continue;
}
if (dfs(i, dest, adj, path, threshhold, vis, n))
{
path.push_back(node);
return true;
}
}
return false;
}
// void dfs2(ll node, vector<vector<ll>> &adj, vector<vector<ll>> &og, ll n, set<pair<ll, ll>> &st)
// {
// if (node != n)
// cout << node << " ";
// else if (node == n)
// cout << node << "\n";
// for (ll i = 1; i <= n; i++)
// {
// if (((adj[node][i] == 0) && (og[node][i] == 1)) && (st.find({node, i}) == st.end()))
// {
// st.insert({node, i});
// dfs2(i, adj, og, n, st);
// }
// }
// }
// bool dfs2(ll node, ll n, vector<vector<ll>> &adj, vector<vector<ll>> &og, vector<vector<ll>> &paths)
// {
// for (ll i = 1; i <= n; i++)
// {
// if ((adj[node][i] == 0) && (og[node][i] == 1))
// {
// }
// }
// }
int main()
{
fastio;
ll n, m;
cin >> n >> m;
vector<vector<ll>> adj(n + 1, vector<ll>(n + 1, -1));
vector<vector<ll>> og(n + 1, vector<ll>(n + 1, -1));
ll sum = 0;
for (ll i = 0; i < m; i++)
{
ll x, y;
ll w = 1;
cin >> x >> y;
og[x][y] = w;
if (adj[x][y] == -1)
{
adj[x][y] = 0;
}
adj[x][y] = w;
if (adj[y][x] == -1)
adj[y][x] = 0;
sum += w;
}
ll ans = 0;
while (sum > 0)
{
vector<ll> path;
vector<ll> vis(n + 1, 0);
bool f = dfs(1, n, adj, path, sum, vis, n);
if (f == true)
{
reverse(path.begin(), path.end());
ll z = path.size();
ll minedgewt = LLONG_MAX;
for (ll i = 0; i < z - 1; i++)
{
minedgewt = min(minedgewt, adj[path[i]][path[i + 1]]);
}
ans += minedgewt;
for (ll i = 0; i < z - 1; i++)
{
adj[path[i]][path[i + 1]] -= minedgewt;
adj[path[i + 1]][path[i]] += minedgewt;
}
}
else
sum /= 2;
}
cout << ans << "\n";
set<pair<ll, ll>> ed;
// unordered_set<ll> ed;
for (ll i = 0; i < ans; i++)
{
vector<ll> v = {1};
int x = 1;
while (x != n)
{
for (ll i = 1; i <= n; i++)
{
if (((adj[x][i] == 0) && (og[x][i] == 1)) && (ed.find({x, i}) == ed.end()))
{
v.push_back(i);
ed.insert({x, i});
x = i;
break;
}
}
}
cout << v.size() << "\n";
for (auto i : v)
cout << (i) << " ";
cout << "\n";
}
}
I hope that you will find these helpful, and will also find it in your hearts to forgive any mistake which might have crept in unknowingly. Also, any feedback is welcome.
Peace!!
Auto comment: topic has been updated by samudra_mitra (previous revision, new revision, compare).
Sugoi! ^_^
Thanks ｡◕‿◕｡
cool
Great job!
Nicely compiled, thanks
It is a helpful initiative,thanks. :)
Good job!, I found them very helpful in my learning of Graph algorithms. Can you please update it to detailed version, because I can't understand some of them fully.
Sorry for bad english :)
please email me your doubts,.. I will be more than happy to help you out..
Email:samudramitra2017@gmail.com
Refer this video for easy implementation of round trip problem:-https://www.youtube.com/watch?v=KSEZ8BbIyHs&t=2s
In the problem Mail Delivery the stack part can be replaced with the following recursive code --
The logic is the same as the stack method. Complete Code — https://ideone.com/FBA8MQ
In your solution for Download Speed in the adjacency matrix creation loop:
There can be cases where the reverse edge(y->x) is also given in the input and this line will make the edgeweight of other edge(x->y) zero even if it was non-zero before. There are 3 test-cases #16, #17 and #18 which give wrong answer because of this.
It should be changed to :
This passed all the test cases
wow!.. thanks a lot!
This is an easier implementation of High_Score : The idea is to find out which nodes can reach the last node through any paths possible. If you have a positive length cycle with any of it's reaching nth node through any path then we can generate arbitrarily large number if this cycle is also connected to 1st node.
Implementation: create an edge list plus an adjacency matrix storing edges in reverse order , then run a dfs from nth node and mark the visited nodes, these are the nodes that can visit nth node.
Now run the bellman ford algorithm, on the nth iteration if any node which can reach nth node and its distance is changed that means the ans is -1.
For Flight discount we can use much simpler method for solving:
we can simply make two graph, one is forward graph and other is reverse graph in which every edge is reversed.
now look at each edge one by one what information you can preprocess beforehand so that you know this edge will come from path 1 -> N
we calculate two array d1 and d2 ,
d1 -> stores the distance of each node from node 1 in forward graph d2 -> stores the distance of each node from node N in reverse graph
now when we look at each edge one by one, we know that distance of path 1->N that includes the edge
will be = d1[u] + d2[v] + w ; // where w -> weight of edge (u,v)
since we can apply discount, we need to find the minimum of
d1[u] + d2[v] + w/2 for all the edges
Very Helpful
why is this code wrong, it prints the cycle in another order, but it should pass i think, as the question says you can print any cycle. https://cses.fi/paste/71f1ae23b2ad8acdcd1093/
Hello. I think there is a mistake in the explanation of Cycle Finding problem. It looks like you are taking only vertex $$$1$$$ as the source, but the graph can be disconnected and there can be negative cycles not reachable from vertex $$$1$$$. To consider all those, we have to find a source for each component and to do so, I think finding topo sort and running bfs in topo sort order would work.
Also, your code for the same problem fails on all testcases. Please look into it.
I have updated the code.. thanks for noticing the error
A simpler approach is to maintain a visited array. Run the Bellman-Ford algorithm starting from every unvisited node. During each iteration, mark all visited vertices as true. If no updates are made in an iteration, you can terminate early. If any vertex remains unvisited after the process, run Bellman-Ford again using it as the new source. However, if updates still occur during the n-th iteration, it indicates the presence of a negative-weight cycle — in that case, trace and report the cycle.
Auto comment: topic has been updated by samudra_mitra (previous revision, new revision, compare).