题意:

　　给一些集合 要求证明所有集合是相同的

　　证明方法是,如果$A∈B$,$B∈A$那么$A=B$成立

　　每一次证明可以得出一个$X∈Y$

　　现在已经证明一些$A∈B$成立

　　求,最少再证明多少次,就可以完成要求

分析

　　其实就等价于给一个有向图,问你再加入多少个边可以使得图变为强连通图

　　给一个图论经典结论:

　　"对于一个有向无环图(DAG)，若想让它成为强连通图，至少需要添加$max(a,b)$条边 $a$为入度为0的点的数量，$b$为出度为0的点的数量"

　　而对于一个有向图,其每个强连通分量都互相可达,也就是只要到达任意一个点,即可到达内部所有的点

　　现在,只要对于强连通分量进行缩点,再新图中统计出入度数即可得到答案

　　*注意,如果强连通分量只有1个,答案应该是0而不是1

#include 
     
      #define ll long long#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pp pair
      
       #define rep(ii,a,b) for(int ii=a;ii<=b;ii++)#define per(ii,a,b) for(int ii=a;ii>=b;ii--)#define show(x) cout<<#x<<"="<
       
        <
        
         >n>>m){    if(m==0) {      cout<
         
          <
          
           >a>>b; add(a,b); } tarjan(); for(int i=1;i<=n;i++){ for(int j=head[i];j;j=e[j].next){ if(belong[i]==belong[e[j].to])continue; dout[belong[i]]++; din[belong[e[j].to]]++; } } int a=0,b=0; for(int i=1;i<=numc;i++){ if(din[i]==0)a++; if(dout[i]==0)b++; } if(numc==1) a=b=0; cout<
           
            <