[백준] 10159 - 저울 (c++)

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

한국정보올림피아드시․도지역본선 > 지역본선 2014 > 고등부 2번

한국정보올림피아드시․도지역본선 > 지역본선 2014 > 중등부 3번

한국정보올림피아드시․도지역본선 > 지역본선 2014 > 초등부 4번

문제 요약

N개의 물건 사이에 M개의 대소관계가 주어진다. (1~N) i물건과 대소관계를 알 수 없는 물건의 개수를 출력해라.

 

풀이 (N^3)

• 플로이드

각 정점에 갈 수 있는 정점수와 올 수 있는 정점수를 구해야 한다. 정방향과 역방향으로 위상정렬dp를 두 번 돌려서 하는 방법이 바로 떠올랐는데 플로이드 한 번으로 모두 구할 수 있단 걸 알고 플로이드로 구현했다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    vector<vector<bool>> d(n+1,vector<bool>(n+1));
    for(int i=0,u,v;i<m;i++)
        cin>>u>>v,d[u][v]=1;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][k]&&d[k][j])
                    d[i][j]=1;

    for(int i=1;i<=n;i++) {
        int cnt=0;
        for(int j=1;j<=n;j++)
            if(!d[i][j]&&!d[j][i])
                cnt++;
        cout<<cnt-1<<'\n';
    }
}