The King’s PRoblem

13 21 21 3 Sample Output
2 題意是將一些點劃分區(qū)域，同時有兩個規(guī)定：1.若有u,v兩個點，u->v且v->u 即n,v兩點可以互相到達形成環(huán)，則一定分在同一區(qū)域思路：Tarjan求強連通分量然后縮點。2.在同一區(qū)域的任意兩點至少存在一條路徑可以相互到達，即（設(shè)同一區(qū)域兩點u,v）有u->v或 v->u。思路：二分圖，很明顯是最小路徑覆蓋，縮點后建新圖，跑個匈牙利得到最大匹配 ans，結(jié)果就為： 縮點后的點數(shù) num 減去 ans。代碼：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int INF = 1e8;const int maxn = 5010;vector<int> G[maxn],G2[maxn];int low[maxn],dfn[maxn]; int vis[maxn],instack[maxn],point[maxn],match[maxn];int n,tot,num;stack<int> S;void init(void){    tot = num = 0;    for(int i=0 ;i<=n ;i++){        G[i].clear();        G2[i].clear();        match[i] = -1;        low[i] = dfn[i] = 0;        vis[i] = instack[i] = point[i] = 0;    }    while(S.size())    S.pop();}void Tarjan(int x){    low[x] = dfn[x] = tot++;    vis[x] = instack[x] = 1;    S.push(x);    for(int i=0 ;i<G[x].size();i++){        int v = G[x][i];        if(!vis[v]){            Tarjan(v);            low[x] = min(low[x],low[v]);        }        else if(instack[v]){            low[x] = min(low[x],dfn[v]);        }    }    if(low[x] == dfn[x]){        while(1){            int t = S.top();            S.pop();            instack[t] = 0;            point[t] = num;             if(t == x)    break;        }        num++;    }}bool find(int x){	for(int i=0 ;i<G2[x].size() ;i++){		int t = G2[x][i];		if(!vis[t]){			vis[t] = 1;			if(match[t] == -1 || find(match[t])){				match[t] = x;				return true;			}		}		}	return false;}int main(){   	int T;   	scanf("%d",&T);   	while(T--){		int m;		scanf("%d%d",&n,&m);		init();   		while(m--){   			int x,y;			scanf("%d%d",&x,&y);			G[x].push_back(y);			}		for(int i=1 ;i<=n ;i++){			if(!vis[i]){				Tarjan(i);			}		}		for(int i=1 ;i<=n ;i++){			for(int j=0 ;j<G[i].size() ;j++){				if(point[i] != point[G[i][j]]){					G2[point[i]].push_back(point[G[i][j]]);				}			}		}		int ans = 0;		for(int i=0 ;i<num ;i++){			memset(vis,0,sizeof(vis));			if(find(i))				ans++;		}		cout << num-ans << endl;			}    return 0;}