转载：http://blog.csdn.net/u014679804/article/details/47053139
题目大意：n个人，从0开始编号，m个关系：表示前者认识后者，若前者认识后者，则前者可以向后者请求帮忙，若后者不认识前者，则前者需要请后者吃顿饭，否则不用。现在编号为0的人要向编号为n-1的人请求帮忙，问至少要请吃多少顿饭？若不能像第n-1个人请求帮忙，输出-1（某人只会向其认识的人请求帮忙，若A认识B，B认识C，则A也可以通过B向C请求帮忙。
能够互相请求帮忙的可以缩成一个点，得到一个新图（DAG图），然后在新图中DFS求出最少次数即可。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <stack> #include <vector> using namespace std; #define MAXN 100005 vector<int> G[MAXN]; int pre[MAXN],low[MAXN],sccno[MAXN],dfs_clock,scc_cnt; stack<int> S; void tarjan(int u) { pre[u]=low[u]=++dfs_clock; S.push(u); for(int i=0;i<(int)G[u].size();i++) { int v=G[u][i]; if(!pre[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) low[u]=min(low[u],pre[v]); } if(low[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=0;i<n;i++) if(!pre[i]) tarjan(i); } vector<int> G2[MAXN]; int n,m; bool flag; int dp(int u){ if(u==sccno[n-1]) { flag=1;return 0;} int ans=0x3f3f3f3f; for(int i=0;i<(int)G2[u].size();i++) ans=min(ans,dp(G2[u][i])+1); return ans; } int main() { int t,i,j,x,y; cin>>t; while(t--) { flag=0; scanf("%d%d",&n,&m); for(i=0;i<n;++i) G[i].clear(); for(i=0;i<m;++i){ scanf("%d%d",&x,&y); G[x].push_back(y); } find_scc(n); for(i=1;i<=scc_cnt;++i) G2[i].clear(); for(i=0;i<n;++i) for(j=0;j<(int)G[i].size();++j) if(sccno[i]!=sccno[G[i][j]]) G2[sccno[i]].push_back(sccno[G[i][j]]); int ans=dp(sccno[0]); if(flag) printf("%d\n",ans); else puts("-1"); } return 0; }测试样例：Example Input
3 4 4 0 1 1 2 2 1 2 3
3 3 0 1 1 2 2 1
3 1 0 1 Example Output
2 1 -1
