hdu 4324 Triangle LOVE <拓扑排序>

链接 http://acm.hdu.edu.cn/showproblem.php?pid=4324

 此题可以一遍拓扑排序判环求解 即只需要找到一个环，就必定存在三元环 证明如下： 假设存在一个n元环，因为a->b有边，b->a必定没边，反之也成立 所以假设有环上三个相邻的点a-> b-> c,那么如果c->a间有边，就已经形成了一个三元环，如果c->a没边，那么a->c肯定有边，这样就形成了一个n-1元环。。。。 所以只需证明n为4时一定有三元环即可，显然成立。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
char map[2500][2500];
int in[2500];
int main( )
{
    int T;
    scanf("%d", &T );
    for( int t=1; t<=T; ++t ){
        printf( "Case #%d: ", t );
        int N, flage=0; 
        scanf( "%d", &N );
        for( int i=0; i<N; ++ i ){
            scanf( "%s", map[i] );
            in[i]=0;
        }
            
        for( int i=0; i<N; ++ i ){
            
            for( int j=0; j<N; ++ j ){
                if( map[i][j]=='1' ){
                    in[j]++;
                }
            }
        }
        for( int i=0, k; i<N; ++i ){
            for(  k=0; k<N; ++k ){
                if( !in[k] )break;
            }
            if( k==N ){
                puts( "Yes" );
                flage=1;
                break;
            }
            else{
            //    printf( "%d ", k );
                in[k]--;
                for( int j=0; j<N; ++j ){
                    if( map[k][j]=='1'&&in[j] )
                        in[j]--;
                }
            }
        }
        if( !flage )puts( "No" );
    } 
    return 0;
}