题目传送
Equivalent SetsTime Limit: 12000/4000 MS (Java/Others) Memory Limit: 104857/104857 K (Java/Others)
Total Submission(s): 6691 Accepted Submission(s): 2413

Problem Description To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.
Input The input file contains multiple test cases, in each case, the first line contains two integers N <= 20000 and M <= 50000.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.
Output For each case, output a single integer: the minimum steps needed.
Sample Input4 0
3 2
1 2
1 3
Sample Output4
2
HintCase 2: First prove set 2 is a subset of set 1 and then prove set 3 is a subset of set 1.

解题思路：先用Tarjan算法对树（森林）中强连通分量进行缩点，之后重新对节点编号，建图，分别求出出度和入度为0的节点数量，max(inde,outde)即为答案，如果对Tarjan算法不了解的最好涉及一下，不然可能看不懂

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map> 
#include<stack>
using namespace std;
const int maxn=2e4+7;
int dfn[maxn],low[maxn];
int scc[maxn];
int index,sccnum;//index DFS遍历到的顺序编号,sccnum标记强联通块的数量 
vector<int>G[maxn];//存图 
int N,M,inde[maxn],outde[maxn];//存入度和出度 
stack<int>S;
void init()//初始化 
{
 	index=0;
 	sccnum=0;
 	memset(inde,0,sizeof(inde));
 	memset(outde,0,sizeof(outde));
 	memset(dfn,0,sizeof(dfn));
 	memset(low,0,sizeof(low));
 	memset(scc,0,sizeof(scc));
 	return ;
}
void Tarjan(int root)
{
 	dfn[root]=low[root]=++index;
 	S.push(root);
 	for(int i=0;i<G[root].size();i++)
 	{
  		int v=G[root][i];
  		if(!dfn[v])//没有被访问过 
  		{
   			Tarjan(v);
   			low[root]=min(low[root],low[v]);
 		}
  		else if(!scc[v])//
  		{
  	 		low[root]=min(low[root],dfn[v]);
  		}
 	}
 	if(low[root]==dfn[root])
 	{
  		sccnum++;//连通块+1
 		while(1)
  		{
   			int x=S.top();
  			S.pop();
   			scc[x]=sccnum;
   			if(x==root)
   			break;
  		}
 	}
 	return ;
}
//int Find(int x)
//{
// while(x!=pre[x])
// x=pre[x];
// return x;
//}
//void John(int x,int y)
//{
// int fx=Find(x);
// int fy=Find(y);
// if(fx!=fy)
// pre[fy]=fx;
// return ;
//}
int main()
{
 	while(~scanf("%d %d",&N,&M))
 	{
  		int i,j;
  		for(i=0;i<=N;i++)
  		G[i].clear();
  		for(i=0;i<M;i++)
  		{
   			int u,v;
   			scanf("%d %d",&u,&v);
   			G[u].push_back(v);
  		}
  		init();
  		for(i=1;i<=N;i++)//数据有可能不是一棵树 而是森林 
  		{
   			if(!dfn[i])
   			Tarjan(i);
  		}
  		for(int u=1;u<=N;u++)
 		{
    			for(int v=0;v<G[u].size();v++)
    			{
     				if(scc[u]!=scc[G[u][v]])//在这WA了好几次 …… 
     				{
      					outde[scc[u]]++;//不是out[u]++,此时用各个连通块的编号即可 
      					inde[scc[G[u][v]]]++;
    				}
    			}
  		}
  		int sum=0,sum1=0;
  		for(i=1;i<=sccnum;i++)
  		{
   			if(!outde[i])
   			sum++;
   			if(!inde[i])
   			sum1++;
  		}
  		printf("%d\n",sccnum==1?0:max(sum,sum1));//需要特判一下 因为有可能强连通缩点以后变成一个点 
 	}
 return 0;
}