题意：有n个命题，已知其中的m个推导，要证明n个命题全部等价（等价具有传递性），最少还需要做出几次推导。
思路：由已知的推导可以建一张无向图，则问题变成了最少需要增加几条边能使图变成强连通图。找出所有的强连通分量，将每一个连通分量视作一个大节点，则整张图变成了一张DAG。设出度为0的大节点个数为b，入度为0的大节点个数为a，则答案就是max(a,b)。
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cstdio> 6 #include<set> 7 #include<map> 8 #include<vector> 9 #include<cstring> 10 #include<stack> 11 #include<cmath> 12 #include<queue> 13 #define clc(a,b) memset(a,b,sizeof(a)) 14 #include <bits/stdc++.h> 15 using namespace std; 16 #define LL long long 17 const int maxn = 20005; 18 const int inf=0x3f3f3f3f; 19 const double pi=acos(-1); 20 int in[maxn],out[maxn]; 21 vector<int>G[maxn]; 22 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt; 23 stack<int>S; 24 25 void dfs(int u) 26 { 27 pre[u]=lowlink[u]=++dfs_clock; 28 S.push(u); 29 for(int i=0; i<G[u].size(); i++) 30 { 31 int v=G[u][i]; 32 if(!pre[v]) 33 { 34 dfs(v); 35 lowlink[u]=min(lowlink[u],lowlink[v]); 36 } 37 else if(!sccno[v]) 38 { 39 lowlink[u]=min(lowlink[u],pre[v]); 40 } 41 } 42 if(lowlink[u]==pre[u]) 43 { 44 scc_cnt++; 45 for(;;) 46 { 47 int x=S.top(); 48 S.pop(); 49 sccno[x]=scc_cnt; 50 if(x==u) 51 break; 52 } 53 } 54 } 55 56 void find_scc(int n) 57 { 58 dfs_clock=scc_cnt=0; 59 clc(sccno,0); 60 clc(pre,0); 61 for(int i=0; i<n; i++) 62 if(!pre[i]) 63 dfs(i); 64 } 65 66 int main() 67 { 68 int t,n,m; 69 scanf("%d",&t); 70 while(t--) 71 { 72 scanf("%d%d",&n,&m); 73 for(int i=0; i<n; i++) 74 G[i].clear(); 75 for(int i=0; i<m; i++) 76 { 77 int u,v; 78 scanf("%d%d",&u,&v); 79 u--; 80 v--; 81 G[u].push_back(v); 82 } 83 find_scc(n); 84 for(int i=1; i<=scc_cnt; i++) 85 in[i]=out[i]=0; 86 for(int u=0; u<n; u++) 87 { 88 for(int i=0; i<G[u].size(); i++) 89 { 90 int v=G[u][i]; 91 if(sccno[u]!=sccno[v]) 92 in[sccno[v]]=out[sccno[u]]=1; 93 } 94 } 95 int a=0,b=0; 96 for(int i=1; i<=scc_cnt; i++) 97 { 98 if(!in[i]) 99 a++; 100 if(!out[i]) 101 b++; 102 } 103 int ans=max(a,b); 104 if(scc_cnt==1) 105 ans=0; 106 printf("%d\n",ans); 107 } 108 return 0; 109 }