题目：
我是超链接
题意：
将一个图划分成若干个部分，要求：1、可以互达的点在一个部分中 2、在一个部分中的点至少单向到达。要求分成部分最少
题解：
1A纪念
第一个要求就是强联通分量缩点，第二个要求就是二分图的最小路径覆盖（最小路径覆盖=顶点数-最大匹配）
代码：
#include <cstdio> #include <cstring> #include <iostream> #define N 5000+5 #define M 100000+5 using namespace std; int tot,nxt[M],point[M],v[M],x[M],y[M]; int low[N],dfs[N],vis[N],belong[N],NN,num,cnt,strack[N]; void addline(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } void cl() { NN=0;cnt=0;num=0; memset(low,0,sizeof(low)); memset(dfs,0,sizeof(dfs)); memset(vis,0,sizeof(vis)); memset(belong,0,sizeof(belong)); tot=0; memset(point,0,sizeof(point)); memset(nxt,0,sizeof(nxt)); memset(v,0,sizeof(v)); } void cl1() { tot=0; memset(point,0,sizeof(point)); memset(nxt,0,sizeof(nxt)); memset(v,0,sizeof(v)); } void tarjan(int now) { low[now]=dfs[now]=++NN; strack[++cnt]=now; vis[now]=true; for (int i=point[now];i;i=nxt[i]) if (!dfs[v[i]]) { tarjan(v[i]); low[now]=min(low[now],low[v[i]]); } else if (vis[v[i]]) low[now]=min(low[now],low[v[i]]); if (low[now]==dfs[now]) { num++; while (strack[cnt]!=now) { belong[strack[cnt]]=num; vis[strack[cnt]]=0; cnt--; } belong[strack[cnt]]=num; vis[strack[cnt]]=0; cnt--; } } bool find(int x,int k) { for (int i=point[x];i;i=nxt[i]) if (vis[v[i]]!=k) { vis[v[i]]=k; if (!belong[v[i]] || find(belong[v[i]],k)) { belong[v[i]]=x; return true; } } return false; } int main() { int T,n,m,i; scanf("%d",&T); while (T--) { cl(); scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); addline(x[i],y[i]); } for (i=1;i<=n;i++) if (!dfs[i]) tarjan(i); cl1(); for (i=1;i<=m;i++) if (belong[x[i]]!=belong[y[i]]) addline(belong[x[i]],belong[y[i]]); memset(belong,0,sizeof(belong)); int ans=0; for (i=1;i<=num;i++) if (find(i,i)) ans++; printf("%d\n",num-ans); } }