阻挡我学习的第一部大概就是我渣到爆的英语吧（我六级也许真的要挂了……） 开始无法理解题意，直接找题解的翻译 然后发现自己看漏了一句（因为太专注红字了把自己绕进去了）
划分州 互通的城市一定属于一个州 一个州之间的每两个城市之间必须有路（也就是说可以是单向） 注意是either or “And the king must insure that in each state we can either go from u to v or go from v to u between every pair of cities (u, v) without passing any city which belongs to other state.”（emmmm我自动补全了i）
所以首先是强连通缩点，这个容易想到 接着就是把州与州之间有单向路径的连接起来 但是因为州之间两个城市必须有路，所以不存在缩点之后有三个连接在一起的情况 就是二分图匹配（再套一发模板） 关于二分图匹配，我本来数组都是开int的，疯狂mle也找不到错误 后来把标记数组改bool （一不小心把part也改bool了也能ac，还有这种操作？）就ac了
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
const int maxn=
5010;
const int vm=maxn*maxn;
const int INF=
0x3f3f3f3f;
vector<int> G[
2*maxn];
int n;
bool mar[maxn][maxn],used[maxn];
int part[maxn];
int uu,vv;
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
void dfs(
int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for (
int i=
0;i<G[u].size();i++)
{
int v=G[u][i];
if (!pre[v])
{
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if (!sccno[v]) lowlink[u]=min(lowlink[u],pre[v]);
}
if (lowlink[u]==pre[u])
{
scc_cnt++;
for (;;)
{
int x=S.top(); S.pop();
sccno[x]=scc_cnt;
if (x==u)
break;
}
}
}
void find_scc(
int n)
{
dfs_clock=scc_cnt=
0;
memset(sccno,
0,
sizeof(sccno));
memset(pre,
0,
sizeof(pre));
for (
int i=
1;i<=n;i++)
if (!pre[i]) dfs(i);
}
bool findp(
int now)
{
int j;
for (j=
1;j<=scc_cnt;j++)
if (mar[now][j]==
1 &&used[j]==
0)
{
used[j]=
1;
if (part[j]==
0 ||findp(part[j]))
{
part[j]=now;
return true;
}
}
return false;
}
int match()
{
int sum=
0;
memset(part,
0,
sizeof(part));
for (
int i=
1;i<=scc_cnt;i++)
{
memset(used,
0,
sizeof(used));
if (findp(i)) sum++;
}
return sum;
}
int main()
{
int m,cases,i,v,xx,yy;
scanf(
"%d",&cases);
while (cases--)
{
scanf(
"%d%d",&n,&m);
for (
int i=
0;i<=n;i++) G[i].clear();
while (m--)
{
scanf(
"%d%d",&uu,&vv);
G[uu].push_back(vv);
}
find_scc(n);
memset(mar,
0,
sizeof(mar));
for (
int u=
1;u<=n;u++)
for (
int j=
0;j<G[u].size();j++)
{
v=G[u][j];
xx=sccno[u],yy=sccno[v];
if (xx!=yy) mar[xx][yy]=
1;
}
printf(
"%d\n",scc_cnt-match());
}
return 0;
}
