2458

초등학생들한테 이런 문제를 풀라고 하는 것도 웃기고 이것 가지고 몇시간 낑낑데는 나도 참 웃기다... 간단히 생각하면 되는데 왜 나는 이 문제를 가지고 stack이니 queue니 하면서 접근 한건지..

비교 가능을 묻는 문제는 그래프 문제로 바꿀 수 있고 각 그래프가 연결 되었는지로 판별 가능하다.

연결 가능성은 floyd warshall 알고리즘으로 한방에 해결 가능하다. 어차피 input도 500개라 사용해도 무방하다. 그런데 나는 방향성을 가진 그래프라 적용할 수 없다고 생각해 계속 문제를 돌려서 풀었다. 양측에서의 도달가능성을 생각해주면 되는 간단한 사실을 알지 못해서 계속 이상한짓 하다가 겨우 풀었다.

아... 아직도 실력이 부족한건지 아니면 마음이 조급해서 그런건지 모르겠다

요즘 문제가 진짜 안풀린다 ㅠㅠ

#include<cstdio> #include<iostream> #include<queue> #include<vector> #include<fstream> using namespace std; int map[501][501]; bool know[501][501]; int indeg[501]; int main(){ int N; int tc; int ret=0; ifstream ifp("input.txt"); ifp>>N>>tc; //scanf("%d %d", &N, &tc); int from, to; for(int i=0; i<tc; i++){ ifp>>from>>to; //scanf("%d %d", &from, &to); map[from][to]=1; } for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(map[i][k]&&map[k][j]) map[i][j]=1; for(int i=1; i<=N; i++){ int check=0; for(int j=1; j<=N; j++) { if(map[i][j] || map[j][i]) check++; } if(check==N-1) ret++; } printf("%d\n", ret); return 0; }