Homework Introduction
图1
/*
题意：找图中最小环
如果一个人的入度为 0 ，肯定不可能成环
删除入度为0 的人和他连接的边
把所有入度为 0 的点删除了，剩下的就是环形
然后 dfs 遍历每个环，记录环的最小值
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int ans = 1e9;
// nxt 能到达的下一个点，入度，-1 代表被删除了
int n, nxt[N], in[N], vis[N];
// 删除所有入度为 0 的点，连接的点的入度也减少 1
void remove(int x) {
vis[x] = -1;
in[nxt[x]] --;
if (in[nxt[x]] == 0 && vis[nxt[x]] != -1)
remove(nxt[x]);
}
// 从当前点 u 开始搜索，进入节点为 fa , 长度为 l
void dfs(int u, int fa, int l) {
// && l 来限制不是第一个点
// 第一个点 l =0
if (u == fa && l) { // 形成了环
ans = min(ans, l);
return ;
}
if (!vis[nxt[u]]) {
vis[nxt[u]] = 1;
dfs(nxt[u], fa, l + 1);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> nxt[i];
in[nxt[i]]++;
}
// 删除所有入度为 0 的点
for (int i = 1; i <= n; i++)
if (in[i] == 0 && vis[i] != -1)
remove(i);
// 搜索环
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs(i, i, 0);
cout << ans;
return 0;
}
可达性统计
//f[i] 代表 i 能到达的点的集合
//x, 能通过边到达 a，b, c
//f[x] = f[a] 并上 f[b] 并上 f[c]
//f[x] , f[a] ,f[b],f[c] 全部有了
//前置条件都满足了
//
//拓扑排序
//从一个点出发，一直走
//
//u -> v , 排序里面一定保证了
//u 在 v 的左边
//
//a b c d e
//
//倒着求 f[e] =1
//
//f[x] = 0101101010 位运算
//f[x][x] =1
//f[x] = f[x] | f[a] | f[b] |f[c]
//bitset<N> f[N]; 每一个都f[i] 都是 N 位的二进制数
//f[i][j] = 1 把 第 j 位赋值为 1
//
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
const int M = 3e4 + 10;
int n, m;
int head[N], ver[M], nxt[M], tot;
bitset<N> f[N];
int in[N];
void add(int x, int y) {
tot++;
ver[tot] = y;
nxt[tot] = head[x];
head[x] = tot;
in[y]++;
}
vector<int> seq; // 拓扑序
void topsort() {
queue<int> q;
for (int i = 1; i <= n; i++)
if (in[i] == 0)
q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
seq.push_back(u); // 拓扑序列
for (int i = head[u] ; i; i = nxt[i] ) {
int v = ver[i];
if (--in[v] == 0)
q.push(v);
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
topsort();
// 从后往前遍历
for (int i = n - 1; i >= 0; i--) {
int j = seq[i];
f[j][j] = 1; // 自己肯定能到达自己
for (int k = head[j] ; k ; k = nxt[k]) {
f[j] |= f[ver[k]];
}
}
for (int i = 1; i <= n; i++)
cout << f[i].count() << endl; // 计算 f[i] 里面 1 的个数
return 0;
}
##车站分级
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
// 每一次列车都需要重置
memset(st, 0, sizeof st);
cnt = 0;
int t;
cin >> t;
for (int j = 1; j <= t; j++) {
cin >> a[++cnt];
st[a[cnt]] = 1;
}
// 指向没出现的点
for (int j = a[1] + 1; j < a[cnt]; j++) {
if (st[j] == 0) { // 当前点j 没出现过
for (int k = 1; k <= cnt; k++) {
if (vis[a[k]][j] == 0) {
add(a[k], j);
vis[a[k]][j] = 1;
}
}
}
}
}
topsort();
cout << ans;
return 0;
}
排序
//1. 有稳定的排序，最大的点的层级等于 点的个数
//2. 存在环，矛盾，最开始的时候有 4 个点，
// 拓扑排序出来只有 2 个点，意味着另外两个环形
//3. 不能唯一确定
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
const int M = 610;
int n, m;
int head[N], ver[M], nxt[M], tot;
int in[N], deg[N]; // deg 用来每一轮的拓扑排序
void add(int x, int y) {
tot++;
ver[tot] = y;
nxt[tot] = head[x];
head[x] = tot;
in[y]++;
}
set<int> s; // 记录点有没有出现过
int f[N]; // 记录点的层级
void topsort(int x) {
int maxx = 0;
vector<int> res; // 存出结果
memset(f, 0, sizeof f);
queue<int> q;
// 入度为 0 的点全部入队
for (int i = 0; i < 26; i++) {
if (deg[i] == 0 && s.count(i))
q.push(i), f[i] = 1;
}
while (q.size()) {
int u = q.front();
q.pop();
res.push_back(u);
maxx = max(maxx, f[u]);
for (int i = head[u]; i ; i = nxt[i]) {
int v = ver[i];
f[v] = max(f[v], f[u] + 1);
if (--deg[v] == 0) {
q.push(v);
}
}
}
// 1. 判断一下最大的层级是否等于 n
if (maxx == n) {
printf("Sorted sequence determined after %d relations: ", x);
for (auto t : res)
cout << char(t + 'A');
cout << ".";
exit(0);
}
// 2. 形成环形,拓扑排序出来的点个数和实际有的不一样，肯定成环
if (res.size() != s.size()) {
printf("Inconsistency found after %d relations.", x);
exit(0);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
char a, opt, b;
cin >> a >> opt >> b;
add(a - 'A', b - 'A'); // 添加边
s.insert(a - 'A');
s.insert(b - 'A');
memcpy(deg, in, sizeof in);
topsort(i); // 增加了一条边，跑一次拓扑排序
}
// 之前没有结束，到这里意味着是没办法确定 顺序的
puts("Sorted sequence cannot be determined.");
return 0;
}
旅行计划
void topsort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
f[i] = 1;
if (in[i] == 0)
q.push(i);
}
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
f[v] = max(f[v], f[u] + 1);
if (--in[v] == 0)
q.push(v);
}
}
}
摄像头
// 标记某个位置有没有摄像头
bool vis[N];
int ans; // 记录砸了几个摄像头
void topsort() {
queue<int> q;
// 摄像头可能照到没有摄像头的位置
for (int i = 0; i <= 500; i++)
if (deg[i] == 0 && vis[i])
q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
if (vis[u])
ans++; // 证明砸了一个摄像头
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (--deg[v] == 0)
q.push(v);
}
}
if (ans == n)
cout << "YES";
else
cout << n - ans;
}
最长路
void topsort() {
queue<int > q;
for (int i = 1; i <= n; i++) {
f[i] = -2147483648;
if (deg[i] == 0)
q.push(i);
}
f[1] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u] ; i; i = nxt[i] ) {
int v = ver[i];
int w = edge[i];
if (--deg[v] == 0)
q.push(v);
f[v] = max(f[v], f[u] + w);
}
}
if (f[n] == -2147483648)
cout << -1;
else
cout << f[n];
}
杂务
int t[N], f[N], ans;
void topsort() {
queue<int> q;
for (int i = 1; i <= n; i++)
if (in[i] == 0)
q.push(i), f[i] = t[i];
while (q.size()) {
int u = q.front();
q.pop();
ans = max(ans, f[u]);
for (int i = head[x] ; i ; i = nxt[i] ) {
int v = ver[i];
if (--in[v] == 0)
q.push(v);
f[v] = max(f[v], f[u] + t[v]);
}
}
cout << ans;
}
B3644
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
const int M = 1e4 + 10;
int head[N], ver[M], nxt[M], tot;
int deg[N];
int n;
vector<int> res;
void add(int x, int y) {
tot++;
nxt[tot] = head[x];
ver[tot] = y;
head[x] = tot;
deg[y]++; // 入度增加
}
void topsort() {
// 1. 建立空的队列
queue<int> q;
// 2. 所有入度为0 的点入队
for (int i = 1; i <= n; i++)
if (deg[i] == 0)
q.push(i);
// 3. 重复直到队列为空
while (q.size()) {
int u = q.front();
q.pop();
res.push_back(u);
// 处理和 u 相连的所有的边
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
deg[v]--; // 边减少，处理入度
if (deg[v] == 0)
q.push(v);
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
while (cin >> x, x) {
add(i, x);
}
}
topsort();
for (auto t : res)
cout << t << " ";
return 0;
}
最大食物链计数
const int mod = 80112002;
int in[N], out[N], f[N];
void topsort() {
queue<int > q;
for (int i = 1; i <= n; i++)
if (in[i] == 0)
q.push(i), f[i] = 1;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (--in[v] == 0)
q.push(v);
f[v] += f[u];
f[v] %= mod;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (out[i] == 0)
ans += f[i], ans %= mod;
}
cout << ans;
}
P3074
int t[N], f[N], ans;
void topsort() {
queue<int> q;
for (int i = 1; i <= n; i++)
if (deg[i] == 0)
q.push(i), f[i] = t[i];
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (--deg[v] == 0)
q.push(v);
f[v] = max(f[v], f[u] + t[v]);
}
}
}
// 先搜索 入度为 0 的点
// 剩下的就是环里面的点
// 再数还有几个环
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
const int M = 1e2 + 10;
int head[N], ver[M], nxt[M], tot;
int in[N];
int n, ans;
bool vis[N]; // dfs 用
void add(int x, int y) {
tot++;
ver[tot] = y;
nxt[tot] = head[x];
head[x] = tot;
in[y]++; // 统计入度
}
void dfs(int x) {
if (vis[x])
return ;
vis[x] = 1;
// 访问 x 连接的所有的点
for (int i = head[x] ; i ; i = nxt[i])
dfs(ver[i]);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
add(i, x);
}
// 先搜索入度为 0 的点
for (int i = 0; i < n; i++)
if (in[i] == 0)
dfs(i), ans++;
// 统计环
for (int i = 0; i < n; i++)
if (vis[i] == 0)
dfs(i), ans++;
cout << ans;
return 0;
}
// 手写链表
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int head, ver[N], nxt[N], tot;
int n; // 代表加入了 n 个点
// 往一个单向链表头部插入一个值
void add(int x) {
tot++; // 新开一个点
ver[tot] = x; // 当前点对应的值为 x
nxt[tot] = head; // 当前点的下一个位置为 head 的值
head = tot; // head 指向 新开的点
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
add(x);
}
// 遍历输出链表的值
for (int i = head; i ; i = nxt[i])
cout << ver[i] << " ";
return 0;
}
// 链式前向星
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; // 点的数量
const int M = 2e5 + 10; // 边的数量
// edge 存储边的权值
int head[N], ver[M], nxt[M], tot, edge[M];
int n, m;
// 增加一条从 x 到 y 权值为 z 的边
void add(int x, int y, int z) {
tot++;
ver[tot] = y;
edge[tot] = z;
nxt[tot] = head[x];
head[x] = tot;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
// add(y,x,z);
}
// 遍历和 i 相连的边
for (int i = 1; i <= n; i++) {
for (int j = head[i] ; j ; j = nxt[j])
cout << ver[j] << " ";
cout << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 2e4 + 10;
int head[N], ver[M], nxt[M], tot;
int n, m, p;
vector<int> ans;
void add(int x, int y) {
tot++;
ver[tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
int main() {
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
cin >> p;
for (int i = head[p] ; i ; i = nxt[i])
ans.push_back(ver[i]);
reverse(ans.begin(), ans.end()); // 反转
cout << ans.size() << endl;
for (auto t : ans)
cout << t << " ";
return 0;
}
Problem
- Status
- Done
- Problem
- 23
- Open Since
- 2026-1-7 0:00
- Deadline
- 2026-1-31 23:59
- Extension
- 24 hour(s)