Article From:https://www.cnblogs.com/nervendnig/p/9124280.html

The meaning of the question is:

  Some sets are required to prove that all sets are the same.

  The proof is that if $A is B$, $B A$, then $A=B$is established.

  Every time it is proved, a $X Y$can be obtained.

  It has now been proved that some of the $A B$are set up

  Ask, at least a few more times, you can complete the request

Analysis

  In fact, it is equivalent to giving a directed graph, asking how many edges you add, so that the graph can be changed into a strongly connected graph.

  To a classic conclusion of graph theory:

  ”For a directed acyclic graph (DAG), if you want to make it a strong connected graph, at least you need to add $max (a, b) side $a$as the number of points with an admission of 0, and $b$for the number of points with an out degree of 0 “.”

  For a directed graph, each strong connected component can reach each other, that is, as long as we reach any point, we can reach all the internal points.

  Now, as long as the strong connected component is reduced, the new statistics can be obtained.

  *Note that if the strong connected component is only 1, the answer should be 0 instead of 1.

#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#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<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<#b<<"]="<<a[b]<<endl
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
int stk[maxn],top,cnt,dfn[maxn],low[maxn],numc,belong[maxn],vis[maxn];
struct node {int to,cost,next;}e[maxm];int head[maxn],nume;
void add(int a,int b,int c=1){e[++nume]=(node){b,c,head[a]};head[a]=nume;}
void tdfs(int now){
	dfn[now]=low[now]=++cnt;
	stk[top++]=now;
	vis[now]=1;
	for(int i=head[now];i;i=e[i].next){
		int to=e[i].to;
		if(!dfn[to]){tdfs(to);low[now]=min(low[now],low[to]);}
		else if(vis[to]) low[now]=min(low[now],dfn[to]);
	}
	if(low[now]==dfn[now]){
		numc++;
		int to;
		do{
			to=stk[--top];
			belong[to]=numc;
			vis[to]=0;
		}while(to!=now);
	}
}
void tarjan(int numv=n){
	for(int i=1;i<=numv;i++){
		if(!dfn[i]) tdfs(i);
	}
}
void ginit(){
	nume=top=numc=cnt=0;
	memset(head,0,sizeof head);
	memset(dfn,0,sizeof dfn);
}
int din[maxn],dout[maxn];

int main(){
//#define test
#ifdef test
  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif

  while(cin>>n>>m){
    if(m==0) {
      cout<<n<<endl;
      continue;
    }
    ginit();
    memset(din,0,sizeof din);
    memset(dout,0,sizeof dout);
    for(int i=0;i<m;i++){
      int a,b;
      cin>>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<<max(a,b)<<endl;
  }

#ifdef test
  fclose(stdin);fclose(stdout);system("out.txt");
#endif
  return 0;
}

  

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *