HDU HDU 3861 The King’s Problem 2011 Multi-University Training Contest 3 - Host by BIT

/*
首先用tarjan算法实现缩点，
然后拆点进行二分匹配（无环图求最大点独立点集）
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN=50005;
int n,m;
vector<int> edge[MAXN];
vector<int> node[MAXN];
int low[MAXN];  // low[u]：是u或u的子树能够追溯到的最早的栈中
int dfn[MAXN]; // dfn[u]：节点u搜索的次序编号(时间戳)  
int INS[MAXN]; //标记是否在栈中
int vis[MAXN];
int link[MAXN]; //link[i]表示二分图右侧i匹配左侧的点的编号
int Stack[MAXN];
int state[MAXN]; // stata[i] = j：第i个点所在的强连通分量的编号
int Time;//时间戳
int top;//栈顶指针
int num;//缩点后点的数目
void tarjan(int x)
{
	low[x]=dfn[x]=Time++;
	Stack[++top]=x;
	INS[x]=1;
	int size=edge[x].size();
	for(int i=0;i<size;i++)
	{
		int v=edge[x][i];
		if(dfn[v]==0)
		{
		tarjan(v);
		low[x]=min(low[x],low[v]);
		}
		else if(INS[v])
		{
		low[x]=min(low[x],dfn[v]);
		}
	}
	   // 如果节点u是强连通分量的根  
	if(low[x]==dfn[x])
	{
		num++;
		int a;
		do
		{
			 a=Stack[top];
			top--;
			INS[a]=0;
			state[a]=num;
		}while(a!=x);
	}
}
int can(int x)//匈牙利算法求增广路
{
	int size=node[x].size();
	for(int j=0;j<size;j++)
	{
		int v=node[x][j];
		if(!vis[v])
		{
			vis[v]=1;
			if(link[v]==-1||can(link[v]))
			{
				link[v]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int Case,u,v;
	scanf("%d",&Case);
	while(Case--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			edge[i].clear();
			node[i].clear();
			low[i]=INS[i]=dfn[i]=0;
			link[i]=-1;
		}
		Time=1;
		top=-1;
		num=0;
		for(int i=0;i<m;i++)
		{
		  scanf("%d%d",&u,&v);
		  edge[u].push_back(v);
		}
		for(int i=1;i<=n;i++)
		if(dfn[i]==0)
		tarjan(i);
		
		for(int i=1;i<=n;i++)
		{
			int size=edge[i].size();
			for(int j=0;j<size;j++)
			{
				int v=edge[i][j];
				if(state[i]!=state[v])//i，v之间有边但他们不在一个强联通分量中，建立一条二分图中的边
				{
				node[state[i]].push_back(state[v]);
				}
			}
		}
		int ans=0;
		//求最小边覆盖集（最大匹配数）
		for(int i=1;i<=num;i++)
		{
			memset(vis,0,sizeof(vis));
			if(can(i))ans++;
		}
		printf("%d\n",num-ans);//点的数目-最大匹配数
	}
}
/*
1 3 2 1 2 1 3
2
*/