细草微风岸

平凡而不平庸

常用链接

统计

最新评论

HDU_3342_Floy判断环

//给定有向路径,判断是否成环。另所有边为1,如果正反向边都有权重,则成环。
#include<iostream>
using namespace std;
#define INF 999999
int D[101][101];
bool floyd(int n)
{
  
int k,i,j;
  
for(k = 0; k < n; k++)
      
for(i = 0; i < n; i++)
          
for(j = 0; j < n; j++)
          
{
             
if(D[i][k]!=INF && D[k][j]!=INF)
             
{
                
if((D[i][k] + D[k][j]) < D[i][j])
                    D[i][j] 
= D[i][k] + D[k][j];
                
if(D[j][i] != INF && D[j][i]!= 0)
                    
return false;

             }

          }

  
return true;
}

int main()
{
  
int n,m,i,j,a,b;
  
while(scanf("%d %d",&n,&m)!=EOF && n)
  
{
    
for(i = 0; i < n; i++)
    
{
       D[i][i] 
= 0;
       
for(j = i+1;j < n;j++)
           D[i][j] 
= D[j][i] = INF;
    }

    
for(i = 0; i < m; i++)
    
{
       scanf(
"%d %d",&a,&b);
       D[a][b]
=1;
    }

    
if(floyd(n))
        puts(
"YES");
    
else
        puts(
"NO");
  }

}


posted on 2011-07-26 23:59 鲍青 阅读(156) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理