Proving Equivalences 与 [[Network of Schools]] 的第二问答案一样。 luogu ## Description 考虑到上述练习在一本普通的线性代数教科书中找到。设 \(A\) 是一个 \(n × n\) 矩阵。证明以下说法是等价的: \((\text{a})\) \(A\) 是可逆的。 \((\text{b})\) \(Ax = b\) 对于每个 \(n × 1\) 矩阵 \(b\) 恰好有一个解。 \((\text{c})\) \(Ax = b\) 对于每个 \(n × 1\) 矩阵 \(b\) 是一致的。 \((\text{d})\) \(Ax = 0\) 仅有平凡解 \(x = 0\)。
(\(a\leftrightarrow b\cap b\leftrightarrow
c\cap c\leftrightarrow d\cap d\leftrightarrow a\) 和 \(a\to b\cap b\to c\cap c\to d\cap d\to a\)
都能表明了这四个说法是等价，但是明显第二种简单很多。) 现在你的任务是证明
\(n\)
个命题全部等价，且你的朋友已经为你做出了 \(m\)
次推导（已知每次推导的内容），你至少还需要做几次推导才能完成整个证明？
## Input 首先是一个正整数，表示测试用例的数量(\(T\leq 100\)) 对于每个测试用例: -
一行，包含两个整数 \(n(1 ≤ n ≤ 2\times
10^4)\) 和 \(m (0 ≤ m ≤ 5\times
10^4)\)：已经证明的陈述的数量和蕴含关系的数量。 - \(m\) 行，每行有两个整数 \(s_1\) 和 \(s_2\)\((1 ≤ s_1,
s_2 ≤ n 且 s_1 ≠ s_2)\)，表示已经证明了陈述 \(s_1\) 蕴含陈述 \(s_2\)。 ## Output 每个测试用例： -
一行，包含需要证明的额外蕴含关系的最小数量，以便证明所有的陈述是等价的。
## Sample Input 1
2
3
4
52
4 0
3 2
1 2
1 31
24
2
代码
(似乎没有平台可以提交这个代码，但是应该是对的)
ans=max(!rdu[i],!cdu[i]) 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using namespace std;
const int N = 20010;
int n, m, dfn[N], low[N], tot, cnt, scc[N], siz[N], top, instk[N], stk[N], cdu[N], rdu[N];
vector<int> e[N];
void tarjan(int x)
{
dfn[x] = low[x] = ++tot;
stk[++top] = x;
instk[x] = 1;
for (int y : e[x])
{ //邻接表存图
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (instk[y])
{
low[x] = min(low[x], low[y]);
}
}
if (dfn[x] == low[x])
{
int y;
++cnt;
do
{
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;
++siz[cnt];
} while (y != x);
}
}
void solve()
{
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(scc, 0, sizeof scc);
memset(siz, 0, sizeof siz);
memset(instk, 0, sizeof instk);
memset(stk, 0, sizeof stk);
memset(cdu, 0, sizeof cdu);
memset(rdu, 0, sizeof rdu);
for (int i = 1; i <= n;i++)
e[i].clear();
cnt = 0, tot = 0, top = 0;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
e[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i++)
{
for (auto v : e[i])
{
if (scc[i] != scc[v])
{
cdu[scc[i]]++;
rdu[scc[v]]++;
}
}
}
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= cnt; i++)
{
if (!cdu[i])
cnt2++;
if (!rdu[i])
cnt1++;
}
if (cnt == 1)
cout << "0\n";
else
cout << max(cnt1, cnt2) << '\n';
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
while (t--)
solve();
}
origin problem
![[../../../../images/Z-attachment/Pasted image 20231223211955.png]]