https://vjudge.net/problem/POJ-3660
传递闭包 , 就是把具有传递性的关系传递开, 通过一些已知的连边求出点与点之间的关系.
设 f[i][j] 表示 i 与 j 是否联通, f[i][j]=f[i][k]&&f[k][j]
再分析每个点, 如果能确定 n-1 个关系, 那就可以确定他的排名.
时间复杂度 O(N^3)
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #define INF (1<<30)
- using namespace std;
- const int maxn=4507;
- int g[maxn][maxn];
- int n,m;
- int main(){
- scanf("%d%d",&n,&m);
- int x,y;
- while(m--){
- scanf("%d%d",&x,&y);
- g[x][y] = 1;
- }
- for(int k=1; k<=n; k++){
- for(int i=1; i<=n; i++){
- for(int j=1; j<=n; j++){
- // g[i][j] = max( g[i][j],(g[i][k] & g[k][j]) );
- if(g[i][k]&&g[k][j]){
- g[i][j] = 1;
- }
- }
- }
- }
- int ans=0;
- for(int i=1; i<=n; i++){
- int cnt=0;
- for(int j=1; j<=n; j++){
- if(g[i][j] || g[j][i]){
- cnt++;
- }
- }
- if(cnt==(n-1)){
- ans++;
- }
- }
- printf("%d\n", ans);
- }
来源: http://www.bubuko.com/infodetail-3185000.html