复习版
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define not !
#define and &&
#define or ||
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
#define N 1010
#define M 10100
typedef long long int ll;
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
int head[N], edge_cnt;
struct Edge {
int to, nxt;
} edges[M];
void addEdge(int u, int v) {
edges[edge_cnt] = (struct Edge) { v, head[u] };
head[u] = edge_cnt++;
}
int n, m, k, indegrees[N], indegrees2[N], a[N], ans[N], ansSize;
void print_graph(void) {
putchar(10);
f(u, 1, n + 1) {
printf("Vertex %ld --> ", u);
for (int e = head[u]; ~e; e = edges[e].nxt)
printf("[%d]\t", edges[e].to);
putchar(10);
}
}
void print_indegrees(void) {
putchar(10);
f(u, 1, n + 1) printf("%d%c", *(indegrees2 + u), u == n ? 10 : 32);
}
bool check(void) {
int u;
f(i, 1, n + 1) {
u = *(a + i);
if (indegrees2[u]) return false;
for (int e = head[u], v; ~e; e = edges[e].nxt) {
v = edges[e].to;
// printf("%d %d\n", a[i], to);
--indegrees2[v];
}
}
return true;
}
void print_ans(void) {
f(i, 0, ansSize) printf("%d%c", *(ans + i), i == ansSize - 1 ? 10 : 32);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
memset(head, ~0, sizeof head);
n = r(), m = r();
for (int u, v; m--;) {
u = r(), v = r();
addEdge(u, v);
++indegrees[v];
}
k = r();
f(i, 0, k) {
memcpy(indegrees2, indegrees, sizeof(indegrees));
f(j, 1, n + 1) *(a + j) = r();
if (not check()) *(ans + ansSize++) = i;
}
print_ans();
// fclose(stdin);
return ~~(0 ^ 0);
}
使用了节点的入度性质 考试成功!
#include <iostream>
#include <vector>
using namespace std;
int n, m, u, v;
void check(vector<vector<int>>& g,
vector<int>& indegrees,
vector<vector<int>>& queries,
vector<int>& ans) {
for (int i = 0; i < queries.size(); ++i) {
vector<int> inbound(indegrees); // 入度表的clone
for (const int cur : queries[i]) {
if (inbound[cur]) {
ans.emplace_back(i);
break;
}
for (const auto& nei : g[cur]) --inbound[nei];
}
}
}
int main(void) {
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> indegrees(n + 1); // 入度表
// build the directed graph
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
++indegrees[v]; // u --> v 那肯定是v的入度加1
}
int k;
cin >> k;
vector<vector<int>> queries(k, vector<int>(n));
for (int i = 0; i < k; ++i)
for (int j = 0; j < n; ++j) cin >> queries[i][j];
vector<int> ans;
check(g, indegrees, queries, ans);
for (const auto& x : ans) cout << x << ' ';
return 0;
}