当我们看到这篇文章后http://blog.sina.com.cn/s/blog_6a44b3340100ko9d.html，估计都不太敢写解析，应该没有比这个更详细更形象的了，把传递闭包 那个外壳剥去 就简单多了，弄清楚传递闭包 跟floyd的关系就可以了，还是直接上代码吧
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; // typedef struct Node{ int from,to; int nex; }; Node edge[200 * 10]; int head[200 + 10],low[200 + 10],dfn[200 + 10],id[200 + 10],Stack[200 + 10],cnt[200 + 10]; bool vis[200 + 10]; int tmpmp[200 + 10][200 + 10],mp[200 + 10][200 + 10]; int vis_num,scc_num,tot,stack_num,tot2; int n; void clear() { memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,-1,sizeof(dfn)); memset(Stack,0,sizeof(Stack)); memset(vis,false,sizeof(vis)); memset(id,0,sizeof(id)); memset(cnt,0,sizeof(cnt)); memset(mp,0,sizeof(mp)); vis_num = 0; scc_num = 0; tot = 0; stack_num = 0; tot2 = 0; } void addedge(int u,int v) { edge[tot].from = u; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void tarjan(int v) { dfn[v] = low[v] = ++vis_num; vis[v] = true; Stack[stack_num++] = v; for(int u=1;u<=n;u++) { if(!tmpmp[v][u])continue; if(dfn[u] == -1) { tarjan(u); low[v] = min(low[u],low[v]); } else if(vis[u]) low[v] = min(dfn[u],low[v]); } int tmp; if(low[v] == dfn[v]) { scc_num++; do { tmp = Stack[--stack_num]; id[tmp] = scc_num; cnt[scc_num]++; vis[tmp] = false; }while(tmp != v); } } void cal() { for(int i=1;i<=n;i++) if(dfn[i] == -1) tarjan(i); } void floyd() { for(int k=1;k<=scc_num;k++) for(int i=1;i<=scc_num;i++) for(int j=1;j<=scc_num;j++) if(mp[i][k] && mp[k][j] && mp[i][j]) mp[i][j] = 0; } int main() { while(scanf("%d",&n) == 1) { clear(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&tmpmp[i][j]); cal(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) if(tmpmp[i][j]) { if(id[i] != id[j]) mp[id[i]][id[j]] = 1; } } floyd(); int ans = 0; for(int i=1;i<=scc_num;i++) if(cnt[i] != 1) ans += cnt[i]; for(int i=1;i<=scc_num;i++) for(int j=1;j<=scc_num;j++) if(mp[i][j]) ans++; printf("%d\n",ans); } return EXIT_SUCCESS; }