2458번: 키 순서

문제 링크

https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

문제 풀이 코드

#include <iostream>
#include <vector>

using namespace std;

const int MN = 501;
bool floyd[MN][MN];

int main(void){

    int N, M; cin>>N>>M;

    for(int i=0; i<M; i++){
        int u,v; cin>>u>>v;
        floyd[u][v]=true;
    }

    for(int k=1; k<=N; k++){
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(floyd[i][k]&&floyd[k][j]){
                    floyd[i][j]=true;
                }
                else continue;
            }
        }
    }

    vector <int> v(N+1);

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(floyd[i][j]){
                v[i]+=1;
                v[j]+=1;
            }
        }
    }
    int cnt=0;
    for(int i=0; i<v.size(); i++){
        if(v[i]==N-1){
            cnt++;
        }
    }
    cout<<cnt;

    return 0;
}