10.1图的定义和相关术语
#include <cstdio>const int MAXN = 100;
int degree[MAXN] = {0};int main() {int n, m, u, v;scanf("%d%d", &n, &m);for (int j = 0; j < m; j++) {scanf("%d%d", &u, &v);degree[u]++;degree[v]++;}for (int i = 0; i < n; i++) {printf("%d", degree[i]);if (i < n - 1) {printf(" ");}}return 0;
}
#include <cstdio>const int MAXN = 100;
int inDegree[MAXN] = {0};
int outDegree[MAXN] = {0};int main() {int n, m, u, v;scanf("%d%d", &n, &m);for (int j = 0; j < m; j++) {scanf("%d%d", &u, &v);outDegree[u]++;inDegree[v]++;}for (int i = 0; i < n; i++) {printf("%d %d\n", inDegree[i], outDegree[i]);}return 0;
}10.2图的存储
#include <cstdio>
#include <cstring>const int MAXN = 100;
int G[MAXN][MAXN];int main() {memset(G, 0, sizeof(G));int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u][v] = G[v][u] = 1;}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d", G[i][j]);printf(j < n - 1 ? " " : "\n");}}return 0;
}
#include <cstdio>
#include <cstring>const int MAXN = 100;
int G[MAXN][MAXN];int main() {memset(G, 0, sizeof(G));int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u][v] = 1;}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d", G[i][j]);printf(j < n - 1 ? " " : "\n");}}return 0;
}
#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];int main() {int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}for (int i = 0; i < n; i++) {printf("%d(%d)", i, (int)G[i].size());for (int j = 0; j < G[i].size(); j++) {printf(" %d", G[i][j]);}printf("\n");}return 0;
}
#include <cstdio>
#include <vector>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];int main() {int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);}for (int i = 0; i < n; i++) {printf("%d(%d)", i, (int)G[i].size());for (int j = 0; j < G[i].size(); j++) {printf(" %d", G[i][j]);}printf("\n");}return 0;
}10.3图的遍历
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];
bool vis[MAXN];void DFS(int u) {vis[u] = true;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!vis[v]) {DFS(v);}}
}int main() {memset(vis, false, sizeof(vis));int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}int blockCount = 0;for (int i = 0; i < n; i++) {if (!vis[i]) {DFS(i);blockCount++;}}printf("%d", blockCount);return 0;
}
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];
bool vis[MAXN];void DFS(int u) {vis[u] = true;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!vis[v]) {DFS(v);}}
}int main() {memset(vis, false, sizeof(vis));int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}int blockCount = 0;for (int i = 0; i < n; i++) {if (!vis[i]) {DFS(i);blockCount++;}}printf(blockCount == 1 ? "Yes" : "No");return 0;
}
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];
int vis[MAXN];bool isCyclic(int u) {vis[u] = 0;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (vis[v] == -1 && isCyclic(v)) {return true;} else if (vis[v] == 0) {return true;}}vis[u] = 1;return false;
}int main() {memset(vis, -1, sizeof(vis));int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);}int isCyclicResult = false;for (int i = 0; i < n; i++) {if (vis[i] == -1 && isCyclic(i)) {isCyclicResult = true;}if (isCyclicResult) {break;}}printf(isCyclicResult ? "Yes" : "No");return 0;
}
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;const int MAXN = 100;
int weight[MAXN];
vector<int> G[MAXN];
bool vis[MAXN];int DFS(int u) {vis[u] = true;int weightSum = weight[u];for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!vis[v]) {weightSum += DFS(v);}}return weightSum;
}int main() {memset(vis, false, sizeof(vis));int n, m, u, v;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) {scanf("%d", &weight[i]);}for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}int maxWeightSum = 0;for (int i = 0; i < n; i++) {if (!vis[i]) {maxWeightSum = max(maxWeightSum, DFS(i));}}printf("%d", maxWeightSum);return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];
bool inQueue[MAXN] = {false};
int layers[MAXN];void BFS(int s) {queue<int> q;q.push(s);inQueue[s] = true;int layer = 0;while (!q.empty()) {int cnt = q.size();for (int i = 0; i < cnt; i++) {int front = q.front();q.pop();layers[front] = layer;for (int j = 0; j < G[front].size(); j++) {int v = G[front][j];if (!inQueue[v]) {q.push(v);inQueue[v] = true;}}}layer++;}
}int main() {int n, m, start, u, v;scanf("%d%d%d", &n, &m, &start);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}BFS(start);for (int i = 0; i < n; i++) {printf("%d", layers[i]);if (i < n - 1) {printf(" ");}}return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;const int MAXN = 100;
vector<int> G[MAXN];
bool inQueue[MAXN] = {false};int BFS(int s, int maxLayer) {queue<int> q;q.push(s);inQueue[s] = true;int layer = 0;int vertexCount = 0;while (!q.empty() && layer <= maxLayer) {int cnt = q.size();vertexCount += cnt;for (int i = 0; i < cnt; i++) {int front = q.front();q.pop();for (int j = 0; j < G[front].size(); j++) {int v = G[front][j];if (!inQueue[v]) {q.push(v);inQueue[v] = true;}}}layer++;}return vertexCount;
}int main() {int n, m, start, maxLayer, u, v;scanf("%d%d%d%d", &n, &m, &start, &maxLayer);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);}int vertexCount = BFS(start, maxLayer);printf("%d", vertexCount);return 0;
}10.4最短路径
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
const int INF = 1e9;struct Edge {int v, dis;Edge(int _v, int _dis) {v = _v, dis = _dis;}
};vector<Edge> G[MAXN];
int d[MAXN];
bool vis[MAXN];void dijkstra(int n, int s) {fill(d, d + MAXN, INF);memset(vis, false, sizeof(vis));d[s] = 0;for (int i = 0; i < n; i++) {int u = -1, minDis = INF;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < minDis) {u = j;minDis = d[j];}}if (u == -1) {return;}vis[u] = true;for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int dis = G[u][j].dis;if (!vis[v] && d[u] + dis < d[v]) {d[v] = d[u] + dis;}}}
}int main() {int n, m, s, t;scanf("%d%d%d%d", &n, &m, &s, &t);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));G[v].push_back(Edge(u, w));}dijkstra(n, s);if (d[t] == INF) {printf("-1");} else {printf("%d", d[t]);}return 0;
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
const int INF = 1e9;struct Edge {int v, dis;Edge(int _v, int _dis) {v = _v, dis = _dis;}
};vector<Edge> G[MAXN];
int d[MAXN];
bool vis[MAXN];void dijkstra(int n, int s) {fill(d, d + MAXN, INF);memset(vis, false, sizeof(vis));d[s] = 0;for (int i = 0; i < n; i++) {int u = -1, minDis = INF;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < minDis) {u = j;minDis = d[j];}}if (u == -1) {return;}vis[u] = true;for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int dis = G[u][j].dis;if (!vis[v] && d[u] + dis < d[v]) {d[v] = d[u] + dis;}}}
}int main() {int n, m, s;scanf("%d%d%d", &n, &m, &s);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));G[v].push_back(Edge(u, w));}dijkstra(n, s);for (int i = 0; i < n; i++) {if (d[i] == INF) {printf("-1");} else {printf("%d", d[i]);}if (i < n - 1) {printf(" ");}}return 0;
} 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
const int INF = 1e9;struct Edge {int v, dis, cost;Edge(int _v, int _dis, int _cost) {v = _v, dis = _dis, cost = _cost;}
};vector<Edge> G[MAXN];
int d[MAXN], c[MAXN];
bool vis[MAXN];void dijkstra(int n, int s) {fill(d, d + MAXN, INF);fill(c, c + MAXN, INF);memset(vis, false, sizeof(vis));d[s] = 0;c[s] = 0;for (int i = 0; i < n; i++) {int u = -1, minDis = INF;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < minDis) {u = j;minDis = d[j];}}if (u == -1) {return;}vis[u] = true;for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int dis = G[u][j].dis;int cost = G[u][j].cost;if (!vis[v]) {if (d[u] + dis < d[v]) {d[v] = d[u] + dis;c[v] = c[u] + cost;} else if (d[u] + dis == d[v] && c[u] + cost < c[v]) {c[v] = c[u] + cost;}}}}
}int main() {int n, m, s, t;scanf("%d%d%d%d", &n, &m, &s, &t);int u, v, dis, cost;for (int i = 0; i < m; i++) {scanf("%d%d%d%d", &u, &v, &dis, &cost);G[u].push_back(Edge(v, dis, cost));G[v].push_back(Edge(u, dis, cost));}dijkstra(n, s);printf("%d %d", d[t], c[t]);return 0;
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
const int INF = 1e9;struct Edge {int v, dis;Edge(int _v, int _dis) {v = _v, dis = _dis;}
};vector<Edge> G[MAXN];
int d[MAXN], pathCount[MAXN];
bool vis[MAXN];void dijkstra(int n, int s) {fill(d, d + MAXN, INF);memset(pathCount, 0, sizeof(pathCount));memset(vis, false, sizeof(vis));d[s] = 0;pathCount[s] = 1;for (int i = 0; i < n; i++) {int u = -1, minDis = INF;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < minDis) {u = j;minDis = d[j];}}if (u == -1) {return;}vis[u] = true;for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int dis = G[u][j].dis;if (!vis[v]) {if (d[u] + dis < d[v]) {d[v] = d[u] + dis;pathCount[v] = pathCount[u];} else if (d[u] + dis == d[v]) {pathCount[v] += pathCount[u];}}}}
}int main() {int n, m, s, t;scanf("%d%d%d%d", &n, &m, &s, &t);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));G[v].push_back(Edge(u, w));}dijkstra(n, s);printf("%d %d", d[t], pathCount[t]);return 0;
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 100;
const int INF = 1e9;struct Edge {int v, dis;Edge(int _v, int _dis) {v = _v, dis = _dis;}
};vector<Edge> G[MAXN];
int d[MAXN], pre[MAXN];
bool vis[MAXN];void dijkstra(int n, int s) {fill(d, d + MAXN, INF);memset(pre, -1, sizeof(pre));memset(vis, false, sizeof(vis));d[s] = 0;for (int i = 0; i < n; i++) {int u = -1, minDis = INF;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < minDis) {u = j;minDis = d[j];}}if (u == -1) {return;}vis[u] = true;for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int dis = G[u][j].dis;if (!vis[v] && d[u] + dis < d[v]) {d[v] = d[u] + dis;pre[v] = u;}}}
}vector<int> path;void DFS(int v, int s) {if (v == s) {path.push_back(v);return;}DFS(pre[v], s);path.push_back(v);
}int main() {int n, m, s, t;scanf("%d%d%d%d", &n, &m, &s, &t);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));G[v].push_back(Edge(u, w));}dijkstra(n, s);DFS(t, s);printf("%d ", d[t]);for (int i = 0; i < path.size(); i++) {printf("%d", path[i]);if (i < (int)path.size() - 1) {printf("->");}}return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 50;
const int INF = 1e9;int d[MAXN][MAXN];void floyd(int n) {for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (d[i][k] != INF && d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) {d[i][j] = d[i][k] + d[k][j];}}}}
}int main() {int n, m;scanf("%d%d", &n, &m);fill(d[0], d[0] + MAXN * MAXN, INF);for (int i = 0; i < n; i++) {d[i][i] = 0;}int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);d[u][v] = d[v][u] = w;}floyd(n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (d[i][j] == INF) {printf("-1");} else {printf("%d", d[i][j]);}if (j < n - 1) {printf(" ");}}printf("\n");}return 0;
}10.5最小生成树
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 500;
const int INF = 1e9;struct Edge {int v, dis;Edge(int _v, int _dis) {v = _v, dis = _dis;}
};vector<Edge> G[MAXN];
int d[MAXN];
bool vis[MAXN];int prim(int n) {fill(d, d + MAXN, INF);memset(vis, false, sizeof(vis));d[0] = 0;int weightSum = 0;for (int i = 0; i < n; i++) {int u = -1, minDis = INF;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < minDis) {u = j;minDis = d[j];}}if (u == -1) {return -1;}vis[u] = true;weightSum += d[u];for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int dis = G[u][j].dis;if (!vis[v] && dis < d[v]) {d[v] = dis;}}}return weightSum;
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));G[v].push_back(Edge(u, w));}int weightSum = prim(n);printf("%d", weightSum);return 0;
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int MAXN = 10000;struct Edge {int u, v, w;Edge(int _u, int _v, int _w) {u = _u, v = _v, w = _w;}
};vector<Edge> edges;bool cmp(Edge a, Edge b) {return a.w < b.w;
}int father[MAXN];int findFather(int x) {int xCopy = x;while (father[x] != x) {x = father[x];}int root = x;x = xCopy;while (father[x] != x) {int fatherX = father[x];father[x] = root;x = fatherX;}return root;
}int kruskal(int n, int m) {for (int i = 0; i < n; i++) {father[i] = i;}int weightSum = 0, edgeCount = 0;sort(edges.begin(), edges.end(), cmp);for (int i = 0; i < m; i++) {int faU = findFather(edges[i].u);int faV = findFather(edges[i].v);if (faU != faV) {father[faU] = faV;weightSum += edges[i].w;edgeCount++;}if (edgeCount == n - 1) {break;}}if (edgeCount != n - 1) {return -1;} else {return weightSum;}
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);edges.push_back(Edge(u, v, w));}int weightSum = kruskal(n, m);printf("%d", weightSum);return 0;
}10.6拓扑排序
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;const int MAXN = 100;vector<int> G[MAXN];
int inDegree[MAXN];
vector<int> topoOrder;void topoSort(int n) {priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.top();q.pop();topoOrder.push_back(u);for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}}G[u].clear();}
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v;for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);inDegree[v]++;}topoSort(n);for (int i = 0; i < topoOrder.size(); i++) {printf("%d", topoOrder[i]);if (i < (int)topoOrder.size() - 1) {printf(" ");}}return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;const int MAXN = 100;vector<int> G[MAXN];
int inDegree[MAXN];bool topoSort(int n) {int vertexCount = 0;priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.top();q.pop();for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}}G[u].clear();vertexCount++;}return vertexCount == n;
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v;for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);inDegree[v]++;}printf(topoSort(n) ? "Yes" : "No");return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;const int MAXN = 100;vector<int> G[MAXN];
int inDegree[MAXN];
vector<int> topoOrder;int topoSort(int n) {int vertexCount = 0;priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.top();q.pop();topoOrder.push_back(u);for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}}G[u].clear();vertexCount++;}return vertexCount;
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v;for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);inDegree[v]++;}int learnCount = topoSort(n);if (learnCount == n) {printf("Yes\n");for (int i = 0; i < topoOrder.size(); i++) {printf("%d", topoOrder[i]);if (i < (int)topoOrder.size() - 1) {printf(" ");}}} else {printf("No\n%d\n", n - learnCount);}return 0;
}10.7关键路径
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;const int MAXN = 100;struct Edge {int v, w;Edge(int _v, int _w) {v = _v, w = _w;}
};vector<Edge> G[MAXN];
int inDegree[MAXN] = {0};
vector<int> topoOrder;
int ve[MAXN], vl[MAXN];
vector<int> activity[MAXN];bool topoSort(int n) {priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.top();q.pop();topoOrder.push_back(u);for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v;inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}if (ve[u] + G[u][i].w > ve[v]) {ve[v] = ve[u] + G[u][i].w;}}}return (int)topoOrder.size() == n;
}int getCriticalPathLength(int n) {memset(ve, 0, sizeof(ve));if (!topoSort(n)) {return -1;}int maxLength = 0;for(int i = 0; i < n; i++) {if(ve[i] > maxLength) {maxLength = ve[i];}}return maxLength;
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));inDegree[v]++;}int pathLength = getCriticalPathLength(n);if (pathLength == -1) {printf("No");} else {printf("Yes\n%d", pathLength);}return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;const int MAXN = 100;struct Edge {int v, w;Edge(int _v, int _w) {v = _v, w = _w;}
};vector<Edge> G[MAXN];
int inDegree[MAXN] = {0};
vector<int> topoOrder;
int ve[MAXN], vl[MAXN];
vector<int> activity[MAXN];bool topoSort(int n) {priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.top();q.pop();topoOrder.push_back(u);for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v;inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}if (ve[u] + G[u][i].w > ve[v]) {ve[v] = ve[u] + G[u][i].w;}}}return (int)topoOrder.size() == n;
}int getCriticalPath(int n) {memset(ve, 0, sizeof(ve));if (!topoSort(n)) {return -1;}int maxLength = 0;for(int i = 0; i < n; i++) {if(ve[i] > maxLength) {maxLength = ve[i];}}fill(vl, vl + n, maxLength);for (int i = (int)topoOrder.size() - 1; i >= 0; i--) {int u = topoOrder[i];for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int w = G[u][j].w;if (vl[v] - w < vl[u]) {vl[u] = vl[v] - w;}}}for (int u = 0; u < n; u++) {for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v;int w = G[u][i].w;int e = ve[u], l = vl[v] - w;if (e == l) {activity[u].push_back(v);}}}return maxLength;
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));inDegree[v]++;}if (getCriticalPath(n) == -1) {printf("No");} else {printf("Yes\n");for (int i = 0; i < n; i++) {sort(activity[i].begin(), activity[i].end());for (int j = 0; j < activity[i].size(); j++) {printf("%d %d\n", i, activity[i][j]);}}}return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;const int MAXN = 100;struct Edge {int v, w;Edge(int _v, int _w) {v = _v, w = _w;}
};vector<Edge> G[MAXN];
int inDegree[MAXN] = {0}, inDegreeOrigin[MAXN] = {0};
vector<int> topoOrder;
int ve[MAXN], vl[MAXN];
vector<int> activity[MAXN];bool topoSort(int n) {priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}while (!q.empty()) {int u = q.top();q.pop();topoOrder.push_back(u);for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v;inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}if (ve[u] + G[u][i].w > ve[v]) {ve[v] = ve[u] + G[u][i].w;}}}return (int)topoOrder.size() == n;
}int getCriticalPath(int n) {memset(ve, 0, sizeof(ve));if (!topoSort(n)) {return -1;}int maxLength = 0;for(int i = 0; i < n; i++) {if(ve[i] > maxLength) {maxLength = ve[i];}}fill(vl, vl + n, maxLength);for (int i = (int)topoOrder.size() - 1; i >= 0; i--) {int u = topoOrder[i];for (int j = 0; j < G[u].size(); j++) {int v = G[u][j].v;int w = G[u][j].w;if (vl[v] - w < vl[u]) {vl[u] = vl[v] - w;}}}for (int u = 0; u < n; u++) {for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].v;int w = G[u][i].w;int e = ve[u], l = vl[v] - w;if (e == l) {activity[u].push_back(v);}}}return maxLength;
}vector<int> criticalPath;
void printCriticalPath(int u) {if(activity[u].size() == 0) {criticalPath.push_back(u);for(int i = 0; i < criticalPath.size(); i++) {printf("%d", criticalPath[i]);if(i < criticalPath.size() - 1) {printf("->");} else {printf("\n");}}criticalPath.pop_back();return;}criticalPath.push_back(u);sort(activity[u].begin(), activity[u].end());for(int i = 0; i < activity[u].size(); i++) {printCriticalPath(activity[u][i]);}criticalPath.pop_back();
}int main() {int n, m;scanf("%d%d", &n, &m);int u, v, w;for (int i = 0; i < m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(Edge(v, w));inDegree[v]++;inDegreeOrigin[v]++;}if (getCriticalPath(n) == -1) {printf("No");} else {printf("Yes\n");for(int i = 0; i < n; i++) {if(inDegreeOrigin[i] == 0 && activity[i].size() != 0) {printCriticalPath(i);}}}return 0;
}