프로 그래 밍 사고 와 실천 Week 7 작업 A - TT 의 마법 고양이

제목 링크: A - TT 의 마법 고양이
제목 설명: TT 에는 마법 고양이 가 있다 는 것 은 잘 알려 져 있다.이날 TT 는 '고양이 와 쥐' 게임 에 전념 하고 있 었 지만 경기 가 시작 되 기도 전에 똑똑 한 마법 고양 이 는 TT 경기 의 최종 결 과 를 알려 주 었 다.TT 는 매우 의아해 했다. 그의 고양이 가 말 을 할 줄 아 는 것 은 물론 이 귀여운 꼬마 가 왜 이렇게 마력 이 있 는 지 의아해 했다.마법 고양 이 는 TT 에 게 사실 게임 승부 표를 가지 고 있 는데 그 위 에 N 개인 과 M 개의 승부 관계 가 있 고 모든 승부 관 계 는 A B 로 A 가 B 를 이 길 수 있 고 승부 관 계 는 전달 성 이 있다 고 말 했다.A 가 B 보다 낫 고 B 가 C 보다 낫 면 A 도 C 보다 낫다.TT 는 고양이 가 어떤 경 기 를 하 든 예측 할 수 있다 고 믿 지 않 기 때문에 얼마나 많은 선수 들 의 승 부 를 미리 알 수 없 는 지 알 고 싶 어 합 니 다. 도와 주 시 겠 습 니까?
Input: 첫 번 째 줄 은 데이터 그룹 수 를 드 립 니 다.각 그룹의 데이터 첫 줄 은 N 과 M (N, M < = 500) 을 드 립 니 다.다음 M 줄 은 줄 마다 A B 를 주 고 A 가 B 를 이 길 수 있다 는 뜻 이다.
Output: 각 조 의 데이터 에 대해 서 는 몇 경기 의 승 부 를 미리 알 수 없습니다.주의 (a, b) 와 (b, a) 등가, 즉 각 이원 조 는 한 번 만 계산 된다.
Sample Input： 3 3 3 1 2 1 3 2 3 3 2 1 2 2 3 4 2 1 2 3 4
Sample Output： 0 0 4
사고방식: 본 문 제 는 Floyd 알고리즘 을 사용 하여 승부 관계 의 전달 성 을 나타 낸다.먼저 N 차원 매트릭스 로 각자 의 승부 관 계 를 보존 하고 0 으로 초기 화해 승부 관계 가 불분명 하 다 는 뜻 을 밝 힌 뒤 플 로 이 드 알고리즘 처리 시 삼중 순환 을 해 승부 관계 의 전달 성 을 확보 해 야 한다.동시에 가지치기 작업 을 하고 이미 승부 관계 가 있 는 조별 만 처리 해 야 한다.수출 할 때 두 사람 간 의 승부 관 계 는 확실 하기 때문에 행렬 의 절반 만 을 고려한다 (대각선 자 체 는 포함 되 지 않 는 다).
요약: 본 문 제 는 기본적으로 알고리즘 을 사용 하 는 동시에 가 지 를 자 르 고 복잡 도 를 줄 여야 한다.
코드:

#include
#include
#include
using namespace std;
int path[510][510];
int main(){
	//freopen("in.txt","r",stdin);
	int T,N,M,A,B,cnt;
	cin>>T;
	while(T--){
		cnt=0;
		memset(path,0,sizeof(path)); 
		cin>>N>>M;
		for(int i=0;i<M;i++){
			cin>>A>>B;
			path[A][B]=1;
		}
		for(int i=1;i<=N;i++)
		  	for(int j=1;j<=N;j++)
		  		if(path[j][i]==1)
		    		for(int k=1;k<=N;k++)
		    			if(path[i][k]==1)
		    				path[j][k]=1;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
				if(i!=j&&path[i][j]==0&&path[j][i]==0)
					cnt++;
		cout<<cnt/2<<endl;
	}
}