// BFS
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
vector<int> graph[N + 1];
vector<int> visited(N + 1, 0); // int visited[N]
// vector<int> level(N + 1, 0); // int level[N]
vector<int> bfstraversal;
// Time Complexity = O(V+E)
void bfs(int source)
{
queue<int> q;
q.push(source);
visited[source] = 1;
while (!q.empty())
{
auto curr_ver = q.front();
q.pop();
bfstraversal.push_back(curr_ver);
// cout<<curr_ver<<" ";
for (auto child : graph[curr_ver])
{
if (visited[child] != 1)
{
q.push(child);
visited[child] = 1;
// level[child] = level[curr_ver] + 1;
}
}
}
for (auto node : bfstraversal)
{
cout << node << " ";
}
cout << endl;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int source;
cin >> source;
bfs(source);
// for (int i = 1; i <= n; i++)
// {
// cout << i << ": " << level[i] << endl;
// }
return 0;
}
// DFS
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
vector<int>graph[N+1];
vector<int>vis(N,0);
// Time Complexity = O(V+E)
void dfs(int vertex)
{
//Take action on vertex after entering the vertex
//if(vis[vertex]) return;
cout<< vertex <<" ";
vis[vertex]=1;
for(auto child : graph[vertex])
{
//cout<<"Parent = " << vertex <<", Child = " << child <<endl;
if(vis[child]==1) continue;
//Take action on child befor entering the child node
dfs(child);
//Take action on child after exiting the child node
}
//Take action on vertex before exiting the vertex
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0; i<m; i++)
{
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int source;
cin>>source;
dfs(source);
return 0;
}
// DIJKSTRA
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int INF = 1e9;
vector<pair<int, int>> graph[N + 1];
vector<int> dist(N, INF);
vector<int> visited(N, 0);
vector<int> parent(N, -1);
// Time Complexity = O(V + ElogV)
// Multi Set Implementation
/*void dijkstra(int source)
{
set<pair<double, int>> st; // double = wt, int = kon node er weight
st.insert({0, source});
dist[source] = 0;
while (st.size() > 0)
{
auto node = *st.begin();
int v = node.second;
int dist_v = node.first;
visited[v]=1;
for (auto child : graph[v])
{
int child_v = child.first;
int wt = child.second;
if (dist[v] + wt < dist[child_v])
// new distance current distance
{
dist[child_v] = dist[v] + wt;
st.insert({dist[child_v], child_v});
}
}
}
}*/
// Priority Queue Implementation
void dijkstra(int source)
{
priority_queue<pair<double, int>> st; // double = weight
// int = kon node er weight
st.push({0, source});
dist[source] = 0;
while (!st.empty())
{
auto node = st.top(); // minimum element
int v = node.second;
int v_dist = node.first;
st.pop();
// if (vis[v])
// continue;
// vis[v] = 1;
for (auto child : graph[v])
{
int child_v = child.first;
int wt = child.second;
if (dist[v] + wt < dist[child_v])
{
dist[child_v] = dist[v] + wt;
st.push({dist[child_v], child_v});
parent[child_v] = v; // Track parent for each node.
}
}
}
}
void printPath(int source, int destination)
{
if (destination == source)
{
cout << source << " ";
return;
}
if (parent[destination] == -1)
{
cout << "No path from " << source << " to " << destination << endl;
return;
}
printPath(source, parent[destination]);
cout << destination << " ";
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, wt;
cin >> u >> v >> wt;
graph[u].push_back({v, wt});
}
int source;
cin >> source;
dijkstra(source);
for (int i = 1; i <= n; i++)
{
cout << "Shortest distance from " << source << " to " << i << " is: " << dist[i] << endl;
printPath(source, i);
cout<<endl;
}
return 0;
}
// BELLMAN FORD
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int INF = 1e9;
vector<pair<int, int>> graph[N + 1];
vector<int> dist(N, INF);
vector<int> visited(N, 0);
vector<int> parent(N, -1);
// Time Complexity = O(V + ElogV)
// Multi Set Implementation
/*void dijkstra(int source)
{
set<pair<double, int>> st; // double = wt, int = kon node er weight
st.insert({0, source});
dist[source] = 0;
while (st.size() > 0)
{
auto node = *st.begin();
int v = node.second;
int dist_v = node.first;
visited[v]=1;
for (auto child : graph[v])
{
int child_v = child.first;
int wt = child.second;
if (dist[v] + wt < dist[child_v])
// new distance current distance
{
dist[child_v] = dist[v] + wt;
st.insert({dist[child_v], child_v});
}
}
}
}*/
// Priority Queue Implementation
void dijkstra(int source)
{
priority_queue<pair<double, int>> st; // double = weight
// int = kon node er weight
st.push({0, source});
dist[source] = 0;
while (!st.empty())
{
auto node = st.top(); // minimum element
int v = node.second;
int v_dist = node.first;
st.pop();
// if (vis[v])
// continue;
// vis[v] = 1;
for (auto child : graph[v])
{
int child_v = child.first;
int wt = child.second;
if (dist[v] + wt < dist[child_v])
{
dist[child_v] = dist[v] + wt;
st.push({dist[child_v], child_v});
parent[child_v] = v; // Track parent for each node.
}
}
}
}
void printPath(int source, int destination)
{
if (destination == source)
{
cout << source << " ";
return;
}
if (parent[destination] == -1)
{
cout << "No path from " << source << " to " << destination << endl;
return;
}
printPath(source, parent[destination]);
cout << destination << " ";
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, wt;
cin >> u >> v >> wt;
graph[u].push_back({v, wt});
}
int source;
cin >> source;
dijkstra(source);
for (int i = 1; i <= n; i++)
{
cout << "Shortest distance from " << source << " to " << i << " is: " << dist[i] << endl;
printPath(source, i);
cout<<endl;
}
return 0;
}
//BMF NEGATIVE
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int INF = 1e9;
vector<vector<int>> graph;
void bellmanFord(int src, int n)
{
vector<int> dist(n, INF);
vector<int> parent(n, -1);
int cycle_start = -1;
dist[src] = 0;
for (int i = 0; i < n - 1; ++i)
{
for (auto edge : graph)
{
int u = edge[0];
int v = edge[1];
int wt = edge[2];
if (dist[u] != INF && dist[u] + wt < dist[v])
{
dist[v] = dist[u] + wt;
parent[v] = u;
}
}
}
for (auto edge : graph)
{
int u = edge[0];
int v = edge[1];
int wt = edge[2];
if (dist[u] != INF && dist[u] + wt < dist[v])
{
cycle_start = v;
break;
}
}
if (cycle_start != -1)
{
cout << "Graph contains a negative cycle." << endl;
vector<int> cycle;
vector<bool> visited(n, false);
while (!visited[cycle_start])
{
cycle.push_back(cycle_start);
visited[cycle_start] = true;
cycle_start = parent[cycle_start];
}
for (int i = 0; i < cycle.size(); ++i)
{
if (cycle[i] == cycle_start)
{
cycle.erase(cycle.begin(), cycle.begin() + i);
break;
}
}
for (int vertex : cycle)
{
cout << vertex << " ";
}
cout << cycle_start << endl;
}
else
{
cout << "No negative cycle found." << endl;
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v, wt;
cin >> u >> v >> wt;
graph.push_back({u, v, wt});
}
int source;
cin >> source;
bellmanFord(source, n);
/*
//Printing Positive Cycle
for(int i=0; i<m; i++)
{
graph[i][2] *= -1;
}
bellmanFord(source,n);
*/
return 0;
}
// FLOYD WARSHALL
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int INF = 1e9;
int dist[N][N];
// Time Complexity = O(N^3)
int main()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = INF;
}
}
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, wt;
cin >> u >> v >> wt;
dist[u][v] = wt;
}
for (int k = 1; k <= n; k++) // k=level,
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (dist[i][k] != INF && dist[k][j] != INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (dist[i][j] == INF)
cout << "I ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}
// FLOYD WARSHALL NEGATIVE
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int INF = 1e9;
int dist[N][N];
int next_vertex[N][N];
int main()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = INF;
}
}
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, wt;
cin >> u >> v >> wt;
dist[u][v] = wt;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (dist[i][j] != INF && i != j)
next_vertex[i][j] = j;
else
next_vertex[i][j] = -1;
}
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (dist[i][k] != INF && dist[k][j] != INF)
{
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
next_vertex[i][j] = next_vertex[i][k];
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
if (dist[i][i] < 0)
{
cout << "Graph contains a negative cycle." << endl;
vector<int> cycle;
int start = i;
cycle.push_back(start);
int current = next_vertex[start][start];
while (current != start)
{
cycle.push_back(current);
current = next_vertex[current][start];
}
cycle.push_back(start);
for (auto vertex : cycle)
{
cout << vertex << " ";
}
cout << endl;
}
}
// No negative cycle found
// cout << "Graph doesn't contain a negative cycle." << endl;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= n; j++)
// {
// if (dist[i][j] == INF)
// cout << "-1 ";
// else
// cout << dist[i][j] << " ";
// }
// cout << endl;
// }
return 0;
}
// PRIMS
#include <bits/stdc++.h>
using namespace std;
const int n = 1e3;
vector<pair<int, int>> graph[n + 1];
vector<int> vis(n, 0);
vector<int> mstNodes;
vector<pair<int, int>> mstEdges; // To store edges in the MST
int cost;
int prims(int src)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, src});
while (!pq.empty())
{
auto it = pq.top();
pq.pop();
int node = it.second;
int wt = it.first;
if (vis[node] == 1)
continue;
// add it to mst
vis[node] = 1;
mstNodes.push_back(node);
cost += wt;
for (auto it : graph[node])
{
int adjnode = it.first;
int weight = it.second;
if (!vis[adjnode])
{
pq.push({weight, adjnode});
mstEdges.push_back({min(node, adjnode), max(node, adjnode)});
}
}
}
return cost;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, wt;
cin >> u >> v >> wt;
graph[u].push_back({v, wt});
graph[v].push_back({u, wt});
}
int src;
cin >> src;
cout << "Total Cost of MST: " << prims(src) << endl;
cout << "Nodes that are in MST: ";
for (auto it : mstNodes)
{
cout << it << " ";
}
cout<<endl;
cout << "Edges in Minimum Spanning Tree:" << endl;
for (auto edge : mstEdges)
{
cout << edge.first << " - " << edge.second << endl;
}
return 0;
}
// DP COIN CHANGE
#include <bits/stdc++.h>
using namespace std;
const int n = 1e4;
int dp[n][n];
int func(int ind, int T, vector<int> &coins)
{
if (ind == 0)
{
if (T % coins[0] == 0)
return T / coins[0];
else
return 1e9;
}
if (dp[ind][T] != -1)
return dp[ind][T];
int notake = 0 + func(ind - 1, T, coins);
int take = INT_MAX;
if (coins[ind] <= T)
take = 1 + func(ind, T - coins[ind], coins);
int ans = min(notake, take);
return dp[ind][T] = ans;
}
int minimumCoinChange(vector<int> &coin, int T)
{
int n = coin.size();
int ans = func(n - 1, T, coin);
if (ans >= 1e9)
return -1;
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
int n;
cin >> n;
vector<int> coins(n);
for (int i = 0; i < n; i++)
{
cin >> coins[i];
}
int target;
cin >> target;
int ans = minimumCoinChange(coins, target);
cout << ans;
return 0;
}
// 01 KNAPSACK
#include <bits/stdc++.h>
using namespace std;
const int n = 10000;
int wt[n], val[n];
int dp[n][n];
int knapsack(int ind, int W)
{
if (ind == 0)
{
if (wt[0] <= W)
return val[0];
else
return 0;
}
if (dp[ind][W] != -1)
return dp[ind][W];
int notake = 0 + knapsack(ind - 1, W);
int take = INT_MIN;
if (wt[ind] <= W)
take = val[ind] + knapsack(ind - 1, W - wt[ind]);
int ans = max(notake, take);
return dp[ind][W] = ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
int noOfitem, TotW;
cin >> noOfitem >> TotW;
for (int i = 0; i < noOfitem; i++)
{
cin >> wt[i] >> val[i];
}
int ans = knapsack(noOfitem - 1, TotW);
cout << ans;
return 0;
}
// TSP DP
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dp;
vector<vector<int>> dist; // adjacent matrix.
int n; // Number of Nodes.
int call(int S, int i)
{
// All the nodes have been visited exactly once.
if (S == ((1 << n) - 1))
{
return dist[i][1]; //Going back to origin from the current city
}
// Subtree has been calculated.
if (dp[S][i] != -1)
return dp[S][i];
// Go to next unvisited node.
int res = INT_MAX;
for (int j = 0; j < n; j++)
{
if ((S & (1 << j)) == 0)
{ // if j'th node is unvisited.
res = min(res, dist[i][j] + call(S | (1 << j), j)); // mark j'th node as visited.
}
}
return dp[S][i] = res;
}
int main()
{
cin >> n;
dist.resize(n, vector<int>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> dist[i][j];
}
}
dp.resize(1 << n, vector<int>(n, -1));
cout << call(1, 1) << endl;
}
/*
4
0 10 15 20
10 0 25 25
15 25 0 30
20 25 30 0
Output: 80
*/
