CFR 349 D. World Tour ( Graph )

Problem - D - Codeforces
Edges are all weighted 1, so we can apply BFS for single source shortest path, for each node as source. This allows us to get all pairwise distances in O( n ^ 2 ). Since we are to find the maximum distance of path a -> b -> c -> d, like always, let us first enumerate the "bridge", which is obvious for b -> c to be. Now we will find maximum a -> b and maximum c -> d, which can be done in O( 1 ) with precomputing and sorting.

vector< int > G[ MAXN ];
int dis[ MAXN ][ MAXN ];
vector< pii > start_dis_rank[ MAXN ];
vector< pii > end_dis_rank[ MAXN ]; // paths that end with u

void solve(){
    int n, m; scanf( "%d%d", &n, &m );
    for( int i = 0; i < m; ++i ){
        int u, v; scanf( "%d%d", &u, &v );
        G[ u ].push_back( v );
    }
    memset( dis, INF, sizeof( dis ) );
    for( int i = 1; i <= n; ++i ){ // SSSP to get all pairwise distances
        queue< pii > que;
        que.push( pii( dis[ i ][ i ] = 0, i ) );
        while( !que.empty() ){
            int u = que.front().second;
            que.pop();
            for( int v : G[ u ] ){
                if( dis[ i ][ v ] > dis[ i ][ u ] + 1 )
                    dis[ i ][ v ] = dis[ i ][ u ] + 1,
                    que.push( pii( dis[ i ][ v ], v ) );
            }
        }
    }
    for( int i = 1; i <= n; ++i ){ // arrange nodes reachable from i by distance
        for( int j = 1; j <= n; ++j ) if( i != j )
            if( dis[ i ][ j ] < INF )
                start_dis_rank[ i ].push_back( pii( dis[ i ][ j ], j ) );
        sort( start_dis_rank[ i ].begin(), start_dis_rank[ i ].end(), greater< pii >() );
    }
    for( int j = 1; j <= n; ++j ){ // arrange nodes ending with j by distance
        for( int i = 1; i <= n; ++i ) if( j != i )
            if( dis[ i ][ j ] < INF )
                end_dis_rank[ j ].push_back( pii( dis[ i ][ j ], i ) );
        sort( end_dis_rank[ j ].begin(), end_dis_rank[ j ].end(), greater< pii >() );
    }
    int ans = 0;
    vector< int > chose;
    for( int b = 1; b <= n; ++b )
        for( int c = 1; c <= n; ++c ) if( b != c && dis[ b ][ c ] < INF ){ // enumerate bridge
            int amax[ 3 ], amax_idx[ 3 ] = { -1, -1, -1 }; // may use up to 3, since a != b AND a != c AND a != d
            for( int i = 0; i < 3; ++i ) if( i < end_dis_rank[ b ].size() )
                amax[ i ] = end_dis_rank[ b ][ i ].first,
                amax_idx[ i ] = end_dis_rank[ b ][ i ].second;
            int dmax[ 3 ], dmax_idx[ 3 ] = { -1, -1, -1 };
            for( int i = 0; i < 3; ++i ) if( i < start_dis_rank[ c ].size() )
                dmax[ i ] = start_dis_rank[ c ][ i ].first,
                dmax_idx[ i ] = start_dis_rank[ c ][ i ].second;
            for( int i = 0; i < 3; ++i ) if( amax_idx[ i ] != -1 && amax_idx[ i ] != c )
                for( int j = 0; j < 3; ++j ) if( dmax_idx[ j ] != -1 && dmax_idx[ j ] != b )
                    if( amax_idx[ i ] != dmax_idx[ j ] )
                        if( ans < amax[ i ] + dis[ b ][ c ] + dmax[ j ] )
                            ans = amax[ i ] + dis[ b ][ c ] + dmax[ j ],
                            chose = { amax_idx[ i ], b, c, dmax_idx[ j ] };
        }
    for( int i = 0; i < 4; ++i )
        printf( "%d%c", chose[ i ], i + 1 == 4 ? '\n' : ' ' );
}