#include<iostream>
#include<iomanip>
using namespace std;
#define MaxNum 10000000;
class edge;
class graph;
class UFSets
{
public:
int n;
int* root;
int* next;
int* length;
UFSets(int size)
{
root = new int[size];
next = new int[size];
length = new int[size];
for (int i = 0; i < size; i++)
{
root[i] = i + 1;
next[i] = i + 1;
length[i] = 1;
}
}
int Find(int v);
void Union(int v, int u)
{
if (length[v - 1] == 1 && length[u - 1] == 1)
{
length[v - 1]++;
root[u - 1] = v;
next[v - 1] = u;
next[u - 1] = v;
}
else if (length[v - 1] > length[u - 1] && length[u - 1] == 1)
{
next[u - 1] = next[v - 1];
next[v - 1] = u;
length[v - 1]++;
root[u - 1] = v;
}
else if (length[v - 1] < length[u - 1] && length[v - 1] == 1)
{
next[v - 1] = next[u - 1];
next[u - 1] = v;
length[u - 1]++;
root[v - 1] = u;
}
else if (length[v - 1] == length[u - 1])
{
u = root[u - 1];
v = root[v - 1];
int a = next[v - 1];
next[v - 1] = next[u - 1];
next[u - 1] = a;
length[v - 1] = length[v - 1] + length[u - 1];
int count = u;
while (next[count - 1] != u)
{
root[count - 1] = v;
length[count - 1] = 1;
count = next[count - 1];
}
root[count - 1] = v;
length[count - 1] = 1;
}
else if (length[v - 1] < length[u - 1])
{
u = root[u - 1];
v = root[v - 1];
int a = next[v - 1];
next[v - 1] = next[u - 1];
next[u - 1] = a;
length[u - 1] = length[v - 1] + length[u - 1];
int count = v;
while (next[count - 1] != v)
{
root[count - 1] = u;
length[count - 1] = 1;
count = next[count - 1];
}
root[count - 1] = u;
length[count - 1] = 1;
}
}
};
class arrayqueue
{
private:
int maxsize;
int front;
int rear;
int queue[100];
public:
arrayqueue(int size = 100)
{
maxsize = size + 1;
front = rear = 0;
}
bool enqueue(int item)
{
if ((rear + 1) % maxsize == front)
{
cout << "the arrayqueue is full" << endl;
return false;
}
queue[rear] = item;
rear = (rear + 1) % maxsize;
return true;
}
int getfront()
{
if (front == rear)
{
cout << "the arrayqueue is empty" << endl;
return false;
}
return queue[front];
}
int isempty()
{
if (front == rear)
return 0;
else
return 1;
}
int pop()
{
int a = queue[front];
front = (front + 1) % maxsize;
return a;
}
};
class edge
{
public:
int start, end;
int weight;
edge(){};
edge(int st, int en, int w);
bool operator >(edge oneedge)
{
if (this->weight > oneedge.weight)
return true;
else
return false;
}
bool operator <(edge oneedge)
{
if (this->weight < oneedge.weight)
return true;
else
return false;
}
};
edge::edge(int st, int en, int w)
{
start = st;
end = en;
weight = w;
}
class graph
{
public:
int vertexNum;
int edgeNum;
int* Mark;
edge* toEdge[100];
int** matrix;
graph(int verticesNum)
{
vertexNum = verticesNum;
edgeNum = 0;
Mark = new int[vertexNum];
for (int i = 0; i < vertexNum; i++)
{
Mark[i] = 0;
}
matrix = (int**)new int*[vertexNum];
for (int i = 0; i < vertexNum; i++)
matrix[i] = new int[vertexNum];
for (int i = 0; i < vertexNum; i++)
for (int j = 0; j < vertexNum; j++)
matrix[i][j] = 0;
}
~graph(){};
int VerticesNum()
{
return vertexNum;
}
int edgenum()
{
return edgeNum;
}
void setedgeeeeee(int start, int end, int weight)
{
edge* e = new edge;
e->start = start;
e->end = end;
e->weight = weight;
toEdge[edgeNum] = e;
edgeNum++;
}
void setedge(int start, int end, int weight)
{
if (matrix[start - 1][end - 1] == 0)
{
edgeNum++;
}
matrix[start - 1][end - 1] = weight;
if (matrix[end - 1][start - 1] == 0)
{
edgeNum++;
}
matrix[end - 1][start - 1] = weight;
}
void delEdge(int start, int end)
{
if (matrix[start - 1][end - 1] != 0)
edgeNum--;
matrix[start - 1][end - 1] = 0;
matrix[end - 1][start - 1] = 0;
}
void DFS(int v)
{
if (Mark[v - 1] == 0)
{
Mark[v - 1] = 1;
cout << v;
}
int i = v - 1;
int j = 0;
while (j<vertexNum)
{
if (matrix[i][j] != 0 && Mark[j] == 0)
DFS(j + 1);
j++;
}
if (j == 5)
return;
else
{
matrix[i][j] = 0;
matrix[j][i] = 0;
DFS(j + 1);
}
}
void Dfstraverse()
{
for (int i = 0; i < vertexNum; i++)
Mark[i] = 0;
for (int i = 0; i < vertexNum; i++)
{
if (Mark[i] == 0)
DFS(i + 1);
}
}
void BFS(int v)
{
int count = 0;
for (int i = 0; i < vertexNum; i++)
{
if (Mark[i] == 1)
count++;
}
if (count == vertexNum)
return;
arrayqueue graphQueue;
cout << v << " ";
Mark[v - 1] = 1;
for (int i = 0; i < vertexNum; i++)
{
if (matrix[v - 1][i] != 0 && Mark[i] != 1)
{
cout << i + 1 << " ";
Mark[i] = 1;
for (int j = 0; j < vertexNum; j++)
{
if (matrix[i][j] != 0 && Mark[j] != 1)
graphQueue.enqueue(j + 1);
}
}
}
BFS(graphQueue.pop());
}
void showthegraph()
{
cout << left;
for (int i = 0; i < vertexNum; i++)
for (int j = 0; j < vertexNum; j++)
{
if (j == 4)
cout << setw(4)<<matrix[i][j] << endl;
else
cout << setw(4)<<matrix[i][j] ;
}
}
void Prim(int v)
{
graph gggg1(vertexNum);
int *u = new int[vertexNum];
int count = 0;
u[count] = v;
Mark[v - 1] = 1;
count++;
int sig = -1;
int sig2 = -1;
while (count != 5)
{
int min = 0;
int i = 0;;
for (int k = 0; k < count; k++)
for (i = 0, min; i < vertexNum; i++)
{
if (matrix[u[k] - 1][i] != 0 && min == 0 && Mark[i] != 1)
{
min = matrix[u[k] - 1][i];
sig = i;
sig2 = u[k] - 1;
}
else if (matrix[u[k] - 1][i] != 0 && Mark[i] != 1)
{
if (matrix[u[k] - 1][i] < min)
{
min = matrix[u[k] - 1][i];
sig = i;
sig2 = u[k] - 1;
}
}
}
u[count] = sig + 1;
Mark[sig] = 1;
count++;
gggg1.setedge(sig2 + 1, sig + 1, matrix[sig2][sig]);
}
gggg1.showthegraph();
}
void Kruskal()
{
graph gggg1(vertexNum);
int **part_matrix = (int**)new int*[vertexNum];
for (int i = 0; i < vertexNum; i++)
part_matrix[i] = new int[vertexNum];
for (int i = 0; i < vertexNum; i++)
for (int j = 0; j < vertexNum; j++)
{
part_matrix[i][j] = matrix[i][j];
}
UFSets graphUF(vertexNum);
int minNum = 0;
int sig1 = -1;
int sig2 = -1;
int count = 0;
while (count != vertexNum - 1)
{
minNum = 0;
for (int i = 0; i < vertexNum; i++)
for (int j = 0; j < vertexNum; j++)
{
if (matrix[i][j] != 0 && part_matrix[i][j] != 0 && minNum == 0 && graphUF.root[i] != graphUF.root[j])
{
minNum = matrix[i][j];
sig1 = i;
sig2 = j;
}
else if (matrix[i][j] != 0 && part_matrix[i][j] != 0 && graphUF.root[i] != graphUF.root[j])
{
if (matrix[i][j] < minNum)
{
minNum = matrix[i][j];
sig1 = i;
sig2 = j;
}
}
}
graphUF.Union(sig1 + 1, sig2 + 1);
part_matrix[sig1][sig2] = 0;
part_matrix[sig2][sig1] = 0;
gggg1.setedge(sig1 + 1, sig2 + 1, matrix[sig1][sig2]);
count++;
}
gggg1.showthegraph();
}
void Dijkstra(int v)
{
int* path = new int[vertexNum];
int* length = new int[vertexNum];
for (int i = 0; i < vertexNum; i++)
{
path[i] = i + 1;
length[i] = 0;
}
length[v - 1] = -1;
int **part_matrix = (int**)new int*[vertexNum];
for (int i = 0; i < vertexNum; i++)
part_matrix[i] = new int[vertexNum];
for (int i = 0; i < vertexNum; i++)
for (int j = 0; j < vertexNum; j++)
{
if (matrix[i][j] != 0)
part_matrix[i][j] = matrix[i][j];
else
part_matrix[i][j] = 1000000;
}
int count
