Equivalent Sets

Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 104857/104857 K (Java/Others)
Total Submission(s): 6755 Accepted Submission(s): 2435

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 Input
4 0
3 2
1 2
1 3

Sample Output
4
2
Hint
Case 2: First prove set 2 is a subset of set 1 and then prove set 3 is a subset of set 1.

Source
2011 Multi-University Training Contest 1 - Host by HNU

就是给你一幅图，问你最多加几条边，使得整个图为强连通图。

我们可以先对每个强连通块染色，然后对于每个强连通块：
有如下情况：

  1. 只有出边
  2. 只有入边
  3. 独立的

每个强连通块肯定不会既有出边又有入边，因为那这个强连通块肯定就不是最大的强连通块了。所以我们统计每个强连通块的入度和出度即可。因为我们让每个强连通块既有出边又有入边即可。

所以答案就是无出边和无入边的联通块的个数的最大值。注意本身就是强连通的情况（特判）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=20010,M=50010;
int n,m,dfn[N],low[N],col[N],cnt,co,vis[N],in[N],out[N],res1,res2;
int head[N],nex[M],to[M],tot;
stack<int> st;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void init(){
	tot=co=res1=res2=cnt=0;	memset(out,0,sizeof out);
	memset(head,0,sizeof head);	memset(in,0,sizeof in);
	memset(dfn,0,sizeof dfn);
}
void tarjan(int x){
	low[x]=dfn[x]=++cnt;	st.push(x);	vis[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]);	low[x]=min(low[to[i]],low[x]);
		}else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
	}
	if(dfn[x]==low[x]){
		co++;
		while(1){
			int u=st.top();	st.pop();	vis[u]=0;
			col[u]=co;	if(x==u)	return ;
		}
	}
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		init();
		for(int i=1;i<=m;i++){
			int a,b;	scanf("%d %d",&a,&b);	add(a,b);
		}
		for(int i=1;i<=n;i++)	if(!dfn[i])	tarjan(i);
		if(co==1){
			puts("0");	continue;
		}
		for(int i=1;i<=n;i++){
			for(int j=head[i];j;j=nex[j]){
				if(col[i]!=col[to[j]])	out[col[i]]++,in[col[to[j]]]++;
			}
		}
		for(int i=1;i<=co;i++)	res1+=(!in[i]),res2+=(!out[i]);
		printf("%d\n",max(res1,res2));
	}
	return 0;
}