문제

문제 링크

문제 접근

  • 이 문제는 사용할 알고리즘을 떠올리지 못하고 결국에 알고리즘 분류를 봤다.
  • 플로이드 와샬이라니.. 바로 어떻게 쓸지 생각이 팍 났다.
  • 한 노드에서 모든 노드로의 길이 있다면 순서를 알 수 있는 친구이다.
  • 왜냐하면 길이 앞에 있는 노드와 뒤에 있는 노드의 개수를 다 알 수 있기 때문이다.

코드

#include <cstdio>
using namespace std;

namespace fio {
    const int BS = 524288;
    char buf[BS];
    char *p = buf + BS;
    inline char readChar() {
        if (p == buf + BS) {
            fread(buf, 1, BS, stdin);
            p = buf;
        }
        return *p++;
    }
    int readInt() {
        char c = readChar();
        while (c < '0') c = readChar();
        int ret = 0;
        while (c >= '0')ret = ret * 10 + c - '0', c = readChar();
        return ret;
    }
}

int ans, n, m, a, b, arr[501][501]; 
int main(){
    n = fio::readInt(); m = fio::readInt();
    for(int i = 0; i < m; i++){
        a = fio::readInt(); b = fio::readInt();
        arr[a][b] = 1;
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][k] + arr[k][j] == 2)arr[i][j] = 1;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int valid = 1;
        for(int j = 1; j <= n; j++){
            if(i == j)continue;
            if(arr[i][j] + arr[j][i] == 0){
                valid = 0; break;
            }
        }
        if(valid)ans++;
    }
    printf("%d", ans);
}

느낀점

  • 위상정렬인줄 알고 한참 고민하다가 실패했다. 알고리즘이 아닌 것 같으면 빨리 다른 알고리즘으로 갈아타봐야겠다…!