链接： ?id=10294
题意 :告诉你n个等价的命题和m个关系比如（u，v）代表u可以推导出v，，问至少需要补充多少条边。
用强连通缩点成一张DAG。
#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <sstream>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <set>#include <map>#define lson o<<1, l, m#define rson o<<1|1, m+1, r#define PII pair<int, int>#define ALL(x) x.begin(),x.end()#define mem(a) memset(a,0,sizeof(a))typedef long long ll;const double pi = acos(-1.0);const int MAX = 0x3f3f3f3f;const ll mod = 1000000007ll;const int N = 20005;const int M = 50005;using namespace std;int n, m, T;int he[N];struct C {int ne, to;} e[M];void add(int id, int x, int y) {e[id].to = y;e[id].ne = he[x];he[x] = id;}stack <int> S;int pre[N], low[N], scc[N], dfs_clock, scc_cnt;void dfs(int u) {pre[u] = low[u] = ++ dfs_clock;S.push(u);for(int i = he[u]; i != -1; i = e[i].ne) {int v = e[i].to;if(pre[v] == 0) {dfs(v);low[u] = min(low[u], low[v]);} else if(scc[v] == 0) {low[u] = min(low[u], pre[v]);}}if(low[u] == pre[u]) {scc_cnt++;for(;;) {int x = S.top(); S.pop();scc[x] = scc_cnt;if(x == u) break;}}}void find_scc() {dfs_clock = scc_cnt = 0;mem(scc);mem(pre);for(int i = 1; i <= n; i++) {if(pre[i] == 0) {dfs(i);}}}int in[N], out[N];int main() {cin >> T;while(T–) {cin >> n >> m;memset(he, -1, sizeof(he));for(int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);add(i, x, y);}find_scc();for(int i = 1; i <= scc_cnt; i++) {in[i] = out[i] = 1;}for(int u = 1; u <= n; u++) {for(int i = he[u]; i != -1; i = e[i].ne) {int v = e[i].to;if(scc[u] != scc[v]) {in[scc[v]] = out[scc[u]] = 0;}}}int a = 0, b = 0;for(int i = 1; i <= scc_cnt; i++) {if(in[i]) a++;if(out[i]) b++;}int ans = max(a, b);if(scc_cnt == 1) ans = 0;printf("%d\n", ans);}return 0;}
关于爱情的句子：情不知所起，一往而情深。
