此题想法挺巧妙的，用folyd算出距离，如果map[i][j]不是INF的话就说明i，j之间有关系，如果是INF就是没关系，如果map[i][j],map[j][i]都是INF，说明i与j没有任何直接边或者间接边相连，那么说明他们之间是完全没关系，那就说这两个数的位置完全无法确定。
// // main.cpp // Richard // // Created by 邵金杰 on 16/8/15. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int maxn=100+5; const int INF=10000000; int map[maxn][maxn]; int N,M; void folyd() { for(int k=1;k<=N;k++) { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { map[i][j]=min(map[i][j],map[i][k]+map[k][j]); } } } } void check() { int vis[maxn]; vector<int> v; memset(vis,0,sizeof(vis)); for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(map[i][j]==INF&&map[j][i]==INF) { if(!vis[i]) {vis[i]=1;v.push_back(i);} if(!vis[j]) {vis[j]=1;v.push_back(j);} } } } printf("%d\n",N-(int)v.size()); } int main() { while(scanf("%d%d",&N,&M)!=EOF) { int s,e; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(i==j) map[i][j]=0; else map[i][j]=INF; } } for(int i=0;i<M;i++) { scanf("%d%d",&s,&e); map[s][e]=1; } folyd(); check(); } return 0; }