SRM480 Div1 Medium(450) NetworkSecurity

NetworkSecurity

トポロジカルソートの降順に処理を行う。自分が接続しているかつ、自分が接続しているクライアントが接続していないサーバーとの間にゲートを設置する。

#include <string>
#include <vector>
#include <set>

using namespace std;

class NetworkSecurity{public:
int secureNetwork( vector <string> clientCable, vector <string> serverCable )
{
    int N = (int)clientCable[0].length();
    int M = (int)serverCable[0].length();

    vector<bool> secure( N );
    vector<vector<bool> > connect( N, vector<bool>( M ) );
    int gate = 0;

    while ( true )
    {
        //  接続先のクライアントが全てセキュアなクライアントを探す
        int cur;
        for( cur=0; cur<N; cur++ )
        if ( ! secure[cur] )
        {
            bool f = true;
            for ( int i=0; i<N; i++ )
                if ( clientCable[cur][i] == 'Y'  &&  ! secure[i] )
                    f = false;
            if ( f )
                break;
        }
        if ( cur >= N )
            break;

        //  このクライアントは接続しているが、
        //  接続先のクライアントは接続していないサーバー間にゲートを設置
        for ( int i=0; i<M; i++ )
        if ( serverCable[cur][i] == 'Y' )
        {
            bool f = true;
            for ( int j=0; j<N; j++ )
                if ( clientCable[cur][j] == 'Y'  &&  connect[j][i] )
                    f = false;
            if ( f )
                gate++;
        }

        //  このクライアントから接続可能なサーバーを調べる
        for ( int i=0; i<M; i++ )
        {
            if ( serverCable[cur][i] == 'Y' )
                connect[cur][i] = true;
            for ( int j=0; j<N; j++ )
                if ( clientCable[cur][j] == 'Y'  &&  connect[j][i] )
                    connect[cur][i] = true;
        }
        
        secure[cur] = true;
    }

    return gate;
}
};