ZOJ3232-白红宇

ZOJ3232

阅读量：5213 次

发布时间：2019-06-14

本文共 1479 字，大约阅读时间需要 4 分钟。

/*	首先给定一个有向图，这个图是原图经过floyd算法求出来的。原图的强连通分量到新图依然是强连通分量，而每个强连通分量都可以用一个环表示。	所以可以先将新图进行缩点，然后形成了一个有向无环图，对其进行floyd的反操作就可以了。*/// include file#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     #include 
                      
                       #include 
                       
                        using namespace std;// typedeftypedef long long ll;// #define read freopen("in.txt","r",stdin)#define write freopen("out.txt","w",stdout)const double Pi = acos(-1.0);const double eps = 1e-6;const int IntMAX = 0x7fffffff;const double DoubleMAX = 1e307;#define TMIN(x,y) ( x
                        
                         =0;i--) { if( !visited[stk[i]]) { rdfs(stk[i] ,scc); scc++; } } for(int i=1;i
                         
                          1) ans+=sz[i]; // Nx = scc-1; memset(xG,0,sizeof(xG)); for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if( G[i][j] && dx[i]!=dx[j] ) { xG[dx[i]][dx[j]] = 1; } } } }int main(){ read; write; while(scanf("%d",&N)==1) { memset(rG,0,sizeof(rG)); for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { scanf("%d",&G[i][j]); if(i==j && G[i][j]) G[i][j] = 0; if(G[i][j]) { rG[j][i] = 1; } } } ans = 0; kosaraju(); // for(int k=1;k<=Nx;k++) { for(int i=1;i<=Nx;i++) { for(int j=1;j<=Nx;j++) { if( xG[i][j] && xG[i][k] && xG[k][j] ) { xG[i][j] = 0; } } } } for(int i=1;i<=Nx;i++) for(int j=1;j<=Nx;j++) { ans+=xG[i][j]; } printf("%d\n",ans); } return 0;}