题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3861
题意：有n个城市，m条路(有方向的），国王想把n个城市划最少个数的州，便于管理。两两相连的城市一定划为一个州，在同一个州的任意两个城市相互之间至少要有一条路径到达，即u到达v或v到达u；每个点都只能在一个州里。问最少需要划分多少个州。
思路：先将n个城市用tarjan算出强联通分量，并将同一连通分量的城市归为一类，一个强连通分量就相当于一个点（可以看作一个城市）。再算出点与点是否相连（两个相连的点可以为一个州），有二分图匹配（匈牙利算法）算出最大匹配数，答案就是强联通分量数减去最大匹配数。
为什么答案是强联通分量数减去最大匹配数？
我们可以这样想，我们先把一个强联通分量的所有城市看作一个点（要缩点）（可看成一个城市），点与点之间相连就可以划分一个州，这是最后的情况，这样这个州的城市都至少有一条路这个到那个。问题是要最少的州，那么我们二分图匹配，算出可以匹配的点，剩下的不可以匹配的就是答案了，所以答案就是强联通分量数减去最大匹配数。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define maxn 100050 using namespace std; struct node{ int v,nxt; }edge[maxn],e[maxn]; int head[maxn],low[maxn],dfn[maxn],vis[maxn],stack[maxn]; int top,cnt,scs,num,ans; int used[maxn],f[maxn],rt[maxn],x[maxn],y[maxn],newhead[maxn]; void init()//初始化 { memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); memset(stack,0,sizeof(stack)); memset(dfn,0,sizeof(dfn)); memset(f,0,sizeof(f)); memset(newhead,-1,sizeof(newhead)); top=cnt=scs=num=0; } void add(int u,int v)//城市和城市相连 { edge[cnt].v=v; edge[cnt].nxt=head[u]; head[u]=cnt++; } void add1(int u,int v)//强联通分量相连 { e[cnt].v=v; e[cnt].nxt=newhead[u]; newhead[u]=cnt++; } void tarjan(int u)//tarjan算出强连通分量，并缩点（将同一强连通分量的城市看作一个点) { low[u]=dfn[u]=++scs; stack[top++]=u; vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].nxt) { int v=edge[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { int t; num++; do { t=stack[--top]; vis[t]=0; rt[t]=num;//缩点，强连通分量编号 }while(t!=u); } } bool find(int x)//匈牙利算法中的是否可以匹配，让位置 { for(int i=newhead[x];i!=-1;i=e[i].nxt) { int v=e[i].v; if(!used[v]) { used[v]=1; if(f[v]==0||find(f[v])) { f[v]=x; return true; } } } return false; } int main() { int t,n,m,ans; cin>>t; while(t--) { init(); cin>>n>>m; for(int i=0;i<m;i++) { cin>>x[i]>>y[i]; add(x[i],y[i]); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); cnt=0; for(int i=0;i<m;i++)//强连通分量相连 { int xx=rt[x[i]],yy=rt[y[i]]; if(xx!=yy)//强连通分量不同 ，由于城市相连，所以 强连通分量相连可能划为一个州 add1(xx,yy); } ans=0; for(int i=1;i<=num;i++)//二分图最大匹配 { memset(used,0,sizeof(used)); if(find(i)) ans++;//最大匹配数 } //cout<<num<<" "<<ans<<endl; cout<<num-ans<<endl; } return 0; }