标签：degree item int 拓扑 入度 ++ vector 排序
拓扑排序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
vector<int> res;
// 入度
vector<int> in_degree(numCourses, 0);
// 邻接表
vector<vector<int>> graph(numCourses);
// 初始化邻接表和入度表
for (const auto &item: prerequisites) {
graph[item[1]].emplace_back(item[0]);
in_degree[item[0]]++;
}
// 存放入度为 0 的顶点
queue<int> q;
for (int i = 0; i < numCourses; ++i)
if (in_degree[i] == 0) q.emplace(i);
// 已经加入拓扑序列的节点个数
int count = 0;
while (!q.empty()) {
// 取出入度为 0 的顶点
int node = q.front();
q.pop();
// 加入拓扑序列
res.emplace_back(node);
count++;
// 遍历邻接表，把入度为 0 的节点从图中断开
for (const auto &next: graph[node]){
// 下个顶点的入度减一
in_degree[next]--;
// 出现入度为 0 的节点，加入队列
if (in_degree[next] == 0) q.emplace(next);
}
}
return count == numCourses ? res : vector<int>();
}
};
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i)
cin >> edges[i].first >> edges[i].second;
// 顶点编号从 1 开始
// 邻接矩阵
vector<vector<int>> graph(n + 1);
// 记录入度
vector<int> in_degree(n + 1, 0);
for (const auto &edge: edges) {
graph[edge.first].emplace_back(edge.second);
in_degree[edge.second]++;
}
// 存放入度为 0 的顶点
queue<int> q;
for (int i = 1; i <= n; ++i)
if (in_degree[i] == 0)
q.emplace(i);
vector<int> res(n);
int count = 0;
// 依次从图中取出入度为 0 的节点
while (!q.empty()) {
int node = q.front();
q.pop();
res[count++] = node;
// 遍历指向的顶点，将其入度减一
for (int i = 0; i < graph[node].size(); ++i) {
// 下个顶点
int next = graph[node][i];
in_degree[next]--;
if (in_degree[next] == 0) q.emplace(next);
}
}
if (count == n) {
for (int i = 0; i < n - 1; ++i)
cout << res[i] << " ";
cout << res[n - 1];
} else {
cout << -1;
}
}
- 有向无环图上有n个点，m条边。求这张图字典序最小的拓扑排序的结果。字典序最小指希望排好序的结果中，比较靠前的数字尽可能小。
- 把存放入度为 0 的队列换成小顶堆即可按字典序输出
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i)
cin >> edges[i].first >> edges[i].second;
// 顶点编号从 1 开始
// 邻接矩阵
vector<vector<int>> graph(n + 1);
// 记录入度
vector<int> in_degree(n + 1, 0);
for (const auto &edge: edges) {
graph[edge.first].emplace_back(edge.second);
in_degree[edge.second]++;
}
// 存放入度为 0 的顶点
priority_queue<int, vector<int>, greater<>> q;
for (int i = 1; i <= n; ++i)
if (in_degree[i] == 0)
q.push(i);
vector<int> res(n);
int count = 0;
// 依次从图中取出入度为 0 的节点
while (!q.empty()) {
int node = q.top();
q.pop();
res[count++] = node;
// 遍历指向的顶点，将其入度减一
for (int i = 0; i < graph[node].size(); ++i) {
// 下个顶点
int next = graph[node][i];
in_degree[next]--;
if (in_degree[next] == 0) q.push(next);
}
}
if (count == n) {
for (int i = 0; i < n - 1; ++i)
cout << res[i] << " ";
cout << res[n - 1];
} else {
cout << -1;
}
}
#include <iostream>
#include <vector>
using namespace std;
// 链式前向星
vector<int> head;
vector<int> nxt;
vector<int> to;
int edgeIndex = 0;
vector<int> in_degree;
void addEdge(int u, int v) {
edgeIndex++;
nxt[edgeIndex] = head[u];
to[edgeIndex] = v;
head[u] = edgeIndex;
}
// 顶点编号和边的编号从 1 开始
void buildGraph(int vertexNum, int edgeNum, vector<pair<int, int>> &edges) {
head.resize(vertexNum, 0);
nxt.resize(edgeNum);
to.resize(edgeNum);
for (const auto &item: edges)
addEdge(item.first, item.second);
}
// 小顶堆存放入度为 0 的顶点编号
vector<int> heap;
int lenOfHeap;
void buildHeap(int max) {
heap.resize(max);
lenOfHeap = 0;
}
// 下标从 0 开始
void adjustHeap(int curIndex) {
int val = heap[curIndex];
int leftChild = 2 * curIndex + 1;
while (leftChild <= (lenOfHeap - 1)) {
// 右孩子更小就选右孩子
if ((leftChild < (lenOfHeap - 1))
&& heap[leftChild] > heap[leftChild + 1])
leftChild++;
// 不需要调整
if (heap[leftChild] >= val) break;
// 调整
heap[curIndex] = heap[leftChild];
curIndex = leftChild;
leftChild = 2 * curIndex + 1;
}
heap[curIndex] = val;
}
void push(int val) {
int curIndex = lenOfHeap;
// 堆大小加一
lenOfHeap++;
// 从下往上调整到合适位置
int parentIndex = (curIndex - 1) >> 1;
while (parentIndex >= 0 && heap[parentIndex] > val) {
// 父节点下移
heap[curIndex] = heap[parentIndex];
curIndex = parentIndex;
parentIndex = (curIndex - 1) >> 1;
}
heap[curIndex] = val;
}
int getTop() {
int res = heap[0];
// 末尾元素移到堆顶
heap[0] = heap[lenOfHeap - 1];
lenOfHeap--;
// 调整堆顶
adjustHeap(0);
return res;
}
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i)
cin >> edges[i].first >> edges[i].second;
buildGraph(n + 1, m + 1, edges);
buildHeap(n + 1);
// 记录入度
in_degree.resize(n + 1, 0);
for (const auto &item: edges)
in_degree[item.second]++;
// 初始状态入度为 0 的点加入堆
for (int i = 1; i < in_degree.size(); ++i)
if (in_degree[i] == 0) push(i);
vector<int> res(n);
int resIndex = 0;
// 取出入度为 0 的点，并删除关联的边
while (lenOfHeap != 0) {
int v = getTop();
res[resIndex++] = v;
// 把所有关联的顶点入度减一
int e = head[v];
while (e > 0) {
in_degree[to[e]]--;
if (in_degree[to[e]] == 0) push(to[e]);
e = nxt[e];
}
}
if (resIndex == n) {
for (int i = 0; i < n - 1; ++i)
cout << res[i] << " ";
cout << res[n - 1];
} else {
cout << -1;
}
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
string alienOrder(vector<string> &words) {
vector<int> in_degree(26, -1);
// 入度为 -1 的就是没出现过的字符
for (const auto &str: words)
for (int i = 0; i < str.length(); ++i)
in_degree[str[i] - 'a'] = 0;
// 建图
vector<vector<int>> graph(26);
for (int i = 0; i < words.size() - 1; ++i) {
string cur = words[i];
string nxt = words[i + 1];
int j = 0;
int len = min(cur.length(), nxt.length());
while (j < len) {
if (cur[j] != nxt[j]) {
// cur[j] 字典序在 nxt[j] 前
graph[cur[j] - 'a'].emplace_back(nxt[j] - 'a');
in_degree[nxt[j] - 'a']++;
break;
}
j++;
}
// 前面相同，但 nxt 长度更小，没有字典序
if (j < cur.length() && j == nxt.length()) return "";
}
queue<int> q;
// 字符种类数
int kinds = 0;
for (int i = 0; i < 26; ++i) {
if (in_degree[i] != -1) kinds++;
if (in_degree[i] == 0) q.push(i);
}
string res = "";
while (!q.empty()) {
int cur = q.front();
q.pop();
// 追加一个字符 cur
res.append(1, cur + 'a');
for (const auto &item: graph[cur]) {
in_degree[item]--;
if (in_degree[item] == 0) q.push(item);
}
}
return res.length() == kinds ? res : "";
}
};
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
int m = stamp.length();
int n = target.length();
// 初始时，入度就是以 i 位置开始，匹配不上的位置的总数，为 m
vector<int> in_degree(n - m + 1, m);
vector<vector<int>> graph(n);
queue<int> q;
// 以 i 开头长度为 m 的字符串与印章对比
for (int i = 0; i <= n - m; ++i) {
for (int j = 0; j < m; ++j) {
if (target[i + j] == stamp[j]) {
// 匹配上的位置，入度减一
in_degree[i]--;
// 入度为 0，入队
if (in_degree[i] == 0) q.push(i);
} else {
// 匹配不上的位置 -> 开头下标 i
graph[i + j].emplace_back(i);
}
}
}
// 同一个位置取消错误不重复统计
vector<bool> visited(n);
vector<int> res(n - m + 1);
int size = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
// 入度为 0 的最后盖章
res[size++] = v;
// 以 v 下标开始盖章
for (int i = 0; i < m; ++i) {
// 这个位置可以由后面的某次盖章处理掉
if (visited[v + i] == true) continue;
// 把仍有错误的位置盖上，变成 true
visited[v + i] = true;
// v + i 位置盖上后，找到所有在 v + i 匹配不上的开头下标 item
// 将 item 开头的位置，入度减小一，表示 v + i 位置匹配上了
for (const auto &item: graph[v + i]) {
in_degree[item]--;
// 如果以 item 开头的位置，后面已经全都匹配上了，也就是入度为 0 了，就入队
if (in_degree[item] == 0) q.push(item);
}
}
}
if (size != n - m + 1) return vector<int>();
// 反转，先加入结果的是最后盖的
reverse(begin(res), end(res));
return res;
}
};
标签：degree,
item,
int,
拓扑,
入度,
++,
vector,
排序
From： https://www.cnblogs.com/sprinining/p/18410625