DIJKSTRA KRUSCAL

void dijkstra(int s){ void Kruskal(){

// mang luu duong di vector<tuple<int, int,int>> MST;
vector<int> d(n+1, INF); int res = 0;
d[s] = 0;
sort(adj.begin(), adj.end());
priority_queue<pair<int, int>,
vector<pair<int, int>>, greater<pair<int, int>>> Q; for(auto it : adj){
Q.push({0, s}); if(MST.size() == n - 1) break;
while(!Q.empty()){ if(Union(get<1>(it), get<2>(it))){
// chon ra dinh co k/c tu s nho nhat res += get<0>(it);
pair<int, int> top = Q.top(); MST.push_back(it);
Q.pop(); }
int u = top.second; }
int kc = top.first;
if(used[u]) continue; if(MST.size() < n -1) cout << 0 << endl;
used[u] = 1; else{
cout << res << endl;
//Relaxation for(auto it : MST)
for(auto it : adj[u]){ cout << get<1>(it) << " " <<
int v = it.first; get<2>(it) << " " << get<0>(it) << endl;
int w = it.second; }
if(d[v] > d[u] + w){ }
d[v] = d[u] + w; DSU
Q.push({d[v], v}); int Find(int u){
} if(u == parent[u]) return u;
} return parent[u] = Find(parent[u]);
}
bool Union(int u, int v){
} u = Find(u);
for(int i = 1; i <= n; i++){ v = Find(v);
cout << d[i] << " "; if(u == v){
} return false;
} }

if(size[u] > size[v]){

swap(u, v);
}
size[u] += size[v];
parent[v] = u;
return true;
}
BELMAN -FORD FLOY
struct edge { const int INF = 10000;
int x, y, w; int n, a[105][105], nxt[105][105];
}; void init(){
cin >> n;
int n, s, t, a[105][105]; for (int i = 1; i <= n; ++i)
int d[105], par[105]; for (int j = 1; j <= n; ++j) {
vector<edge> e; cin >> a[i][j];
if (i != j && a[i][j] < INF)
int main(){ nxt[i][j] = j;
freopen("BN.INP", "r", stdin); else
freopen("BN.OUT", "w", stdout); nxt[i][j] = -1;
}
cin >> n >> s >> t; }
for (int i = 1; i <= n; i++) { void Floyd(){
for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; ++k)
int w; for (int i = 1; i <= n; ++i)
cin >> w; for (int j = 1; j <= n; ++j)
if (w != 10000 && i != j) if (a[i][k] < INF && a[k][j] < INF &&
e.push_back({ i, j, w }); a[i][j] > a[i][k] + a[k][j]) {
} a[i][j] = a[i][k] + a[k][j];
} nxt[i][j] = nxt[i][k];
fill(d + 1, d + n + 1, 1e9); }
d[s] = 0; }
par[s] = -1; int main(){
freopen("DN.INP", "r", stdin);
for (int i = 1; i <= n - 1; i++) { freopen("DN.OUT", "w", stdout);
for (auto [u, v, w] : e) { init();
if (d[u] < 1e9 && d[v] > d[u] + w) { Floyd();
d[v] = d[u] + w; int res = -1, u = -1, v = -1;
par[v] = u; for (int i = 1; i <= n; ++i)
} for (int j = 1; j <= n; ++j)
} if (i != j && a[i][j] < INF) {
} if (res == -1 || a[i][j] > res ||
for (auto [u, v, w] : e) { (a[i][j] == res && tie(i, j) < tie(u, v))) {
if (d[u] < 1e9 && d[v] > d[u] + w) { res = a[i][j];
cout << -1 << endl; u = i;
return 0; v = j;
} }
} }
if (d[t] == 1e9) { if (res == -1) {
cout << 0 << endl; cout << 0 << endl;
return 0; return 0;
} }
vector<int> path; vector<int> path;
for (int x = t; x != -1; x = par[x]) int tmp = u;
path.push_back(x); while (tmp != v) {
reverse(path.begin(), path.end()); path.push_back(tmp);
tmp = nxt[tmp][v];
cout << d[t] << endl; if (tmp == -1) {
for (auto x : path) cout << 0 << endl;
cout << x << ' '; return 0;
cout << endl; }
} }
path.push_back(v);

cout << u << ' ' << v << ' ' << res << endl;
for (int node : path)
cout << node << ' ';
cout << endl;
}
EULER HAMINLTON
void findEC(int s){ void findHC(int step){
stack<int> stk; int v = path[step - 1];
stk.push(s); for(auto it : adj[v]){
while(!stk.empty()){ if(step == n && it == path[0]){
int v = stk.top(); vector<int> tmp = path;
if(adj[v].size() != 0){ tmp.push_back(it);
int u = *adj[v].begin(); HC.push_back(tmp);
stk.push(u); }
adj[v].erase(u); else{
adj[u].erase(v); if(!used[it]){
} used[it] = 1;
else{ path.push_back(it);
EC.push_back(v); findHC(step + 1);
stk.pop(); path.pop_back();
} used[it] = 0;
} }
reverse(EC.begin(), EC.end()); }
} }
}

KIỂM TRA CẠNH CẦU PRIME

for(int i = 1; i <= n - 1; i++) void prim(int u){
{ int d = 0;
for(int j = i + 1; j <= n; j++) vector<edge> mst;
{ visited[u] = true;
if(a[i][j]) while (mst.size()!= n-1){
{ int min_w = 1e9+7;
a[i][j] = 0; int x, y;
a[j][i] = 0; for (int i=1;i<=n;i++){
memset(vs,0,sizeof(vs)); if (visited[i]){
cnt = 0; for (auto it:vt[i]){
for(int k = 1; k <= n; k++) if (!visited[it.first]){
{ if (it.second<min_w){
if(!vs[k]) min_w = it.second;
{ y = i;
cnt++; x = it.first;
DFS(k); }
} }
} }
if(cnt > tplt) cout << i << ' ' << j }
<< "\n"; }
a[i][j] = 1; mst.push_back({x, y, min_w});
a[j][i] = 1; visited[x] = true;
} d+=min_w;
} }
} cout << "dH = " << d << "\n";
for (auto it:mst){
if (it.u>it.v) swap(it.u, it.v);
cout << it.u << ' ' << it.v << '\n';
}
}