6156 - Cow Contest

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

처음에는 위상정렬인가 생각했다. 위상정렬로 어떻게 하지 생각하다가 필요없단 걸 깨달았다.
한 소가 나머지 소들과 한번씩 붙어봤다면 (모두를 알면) 자신의 순위를 알 수 있다.

소를 하나의 정점으로 생각하면 어떤 한 정점과 연결된 선의 갯수가 V-1(자신을 제외한 나머지)개 라면 순위를 알 수 있다.

들어오는 간선(indegree) + 나가는 간선(outdegree) = V-1 (문제에선 N-1) 이면 된다. 정점끼리 서로 연결되었는 지는 방향 그래프를 유지해야하고, 셀 때만 구분없이 세면 된다.

7 6
4 3
3 2
1 2
2 5
5 6
5 7

는 2번 소, 5번 소 = 2개 가 나와야 한다.

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

int main(){
    int i, j, k, N, M;
    scanf("%d %d", &N, &M);
    bool determine[100][100]={};
    while(M--){
        int s, e;
        scanf("%d %d ", &s, &e);
        determine[s-1][e-1] = true;
    }
    for(k=0; k<N; ++k)
        for(i=0; i<N; ++i)
            for(j=0; j<N; ++j)
                determine[i][j] |= determine[i][k] && determine[k][j];
    
    int ans = 0;
    for(i=0; i<N; ++i){
        int cnt = 0;
        for(j=0; j<N; ++j){
            if(i==j) continue;
            cnt += determine[i][j] || determine[j][i];
        }
        ans += cnt == N-1;
    }
    printf("%d", ans);
    return 0;
}