--hdu 1151 - 双向路径搜索解决覆盖问题

http://acm.hdu.edu.cn/showproblem.php?pid=1151

伞兵可以降落到图上的任意一个点，用最少的伞兵在单向道路上走完所有的点

解决：对一个点双向dfs，目的在于找到任意一个其他伞兵未访问的非起点，只要找到这个点，则可以保证这条路径是最佳的；

因为路是单向的，所以从这个点出发后，就不会再次回到这个点（题目中保证没有环）。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int ms[125][125];
int vis[125];
int n,m;
bool dfs(int u){
bool wala = false;
for(int i = 1;i<=n;i++){
if(vis[i] == 0 &&ms[u][i]){
vis[i] = 1;
dfs(i);
wala = true;
break;
}else if(ms[u][i] && dfs(i)){
wala = true;
break;
}
}
return wala;
}
bool re_dfs(int u){
bool wala = false;
for(int i = 1;i<=n;i++){
if(vis[i] == 0&&ms[i][u]){
vis[i] = 1;
re_dfs(i);
wala = true;
break;
}else if(ms[i][u] &&re_dfs(i)){
wala = true;
break;
}
}
return wala;
}
int main(){
int t ;
scanf("%d",&t);
while(t--){
int ans = 0;
memset(ms,0,sizeof(ms));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
int u,v;
for(int i = 0;i<m;i++){
scanf("%d%d",&u,&v);
ms[u][v] = 1;
}
for(int  i = 1;i <= n;i++){
if(!vis[i]){
vis[i] = 1;
dfs(i);
re_dfs(i);
ans ++;
}
}
printf("%d\n",ans);
}
}