Notes

//----------bfs--------------
/*#include<bits/stdc++.h>
#include<queue>
using namespace std;

const int MAX =100;
int adj[MAX][MAX];
bool visited[MAX];
int n;

void bfs(int start)
{
queue<int>q;
q.push(start);
visited[start]=true;

while(!q.empty())
{
int cur =q.front();
q.pop();
cout<<cur<<" ";

for(int i=0; i<n;i++)
{
if(adj[cur][i]==1 && !visited[i])
{
visited[i]=true;
q.push(i);
}
}
}
}
int main()
{
int m;
cout<<"Enter the number of Vertex And Edges: ";
cin>>n>>m;
cout<<"Enter the endsPoints of Edge: ";
for(int i=0; i<m; i++)
{
int u,v;
cin>>u>>v;
adj[u][v]=adj[v][u]=1;
}
int start;
cout<<"Enter the starting Vertex For BFS: ";
cin>>start;
bfs(start);
cout<<endl;
}
*/

//---------dfs---------------
/*
#include<bits/stdc++.h>
#include<stack>
using namespace std;

const int MAX = 100;
int adj[MAX][MAX];
bool visited[MAX];
int n;

void dfs(int start)
{
stack<int>s;
s.push(start);
visited[start] = true;

while(!s.empty())
{
int cur = s.top();
s.pop();
cout<<cur<<" ";

for(int i=0; i<n;i++)
{
if(adj[cur][i]==1 && !visited[i])
{
visited[i] =true;
s.push(i);
}
}
}
}

int main()
{
int m;
cout<<"Enter the Vertex and Edges: ";
cin>>n>>m;

for(int i=0; i<m; i++)
{
int u,v;
cout<<"Enter the endsPoints Of All Vertex: "<<i+1<<": ";
cin>>u>>v;
adj[u][v]=adj[v][u]=1;
}

int start;
cout<<"Enter the starting vertex for DFS: ";
cin>>start;
dfs(start);
cout<<endl;
}

*/

//-------------Kruskal
/*
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int parent[N];
int siz[N];

void mek(int v)
{
parent[v] = v;
siz[v] = 1;
}

int fnd(int v)
{
if(v == parent[v]) return v;
return parent[v] = fnd(parent[v]);
}

void uni(int a, int b)
{
a = fnd(a);
b = fnd(b);
if(a != b)
{
if(siz[a] < siz[b])
{
swap(a,b);
}
parent[b] = a;
siz[a] += siz[b];
}
}

int main()
{
int v, e;
5 >> v >> e;
typedef pair<int,pair<int,int>> edge;
typedef vector<edge> ve;
typedef greater<edge> gr;
priority_queue<edge, ve, gr> pq;
for(int i = 0; i < e; i++)
{
int u, v, wt;
cin >> u >> v >> wt;
pq.push({wt,{u,v}});
}
for(int i = 1; i <= v; i++) mek(i);
int cost = 0;
while(!pq.empty())
{
int wt = pq.top().first;
int u = pq.top().second.first;
int v = pq.top().second.second;
pq.pop();
if(fnd(u) == fnd(v)) continue;
uni(u,v);
cost += wt;
cout << u << " " << v << endl;
}
cout<<cost<<endl;
}

*/


//----------------Prims---------------
/*

#include<bits/stdc++.h>
using namespace std;
#define V 5
#define INF 999999

int main()
{
int G[V][V] =
{
{0,5,0,10,7},
{5,6,0,0,0},
{0,6,0,3,0},
{10,0,3,0,9,},
{7,0,0,9,0}
};

int selected[V];
memset(selected,false,sizeof(selected));
selected[0]=true;
int noEdg = 0;
int x,y;


while(noEdg <V-1)
{
x=0;
y=0;
int min = INF;
for(int i=0; i<V; i++)
{
if(selected[i])
{
for(int j=0; j<V; j++)
{
if(!selected[j] && G[i][j])
{
if(min>G[i][j])
{
min = G[i][j];
x=i;
y=j;
}
}
}
}
}
cout<<x<<"-"<<y<<" : "<<G[x][y]<<endl;
selected[y]=true;
noEdg++;
}
}

*/