hdu 1285 경기 순위 확정(가장 간단 한 토폴로지 정렬)

경기 순 위 를 확정 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4148    Accepted Submission(s): 1547
 
Problem Description
N 개 경기 팀(1<N>=500)이 있 고 번 호 는 1,2,3,...N 이 경 기 를 하고 경기 가 끝 난 후에 심판 위원 회 는 모든 참가 팀 을 이동 한 후에 순서대로 순 위 를 매 겨 야 한다.그러나 현재 심판 위원 회 는 각 팀 의 경기 성적 을 직접 얻 을 수 없고 매 경기 의 결과,즉 P1 이 P2 를 이 기 는 것 만 알 고 있 으 며 P1,P2 로 순 위 를 매 길 때 P1 이 P2 앞 에 있다 고 표시 한다.지금 프로그램 을 짜 서 순 위 를 정 하 세 요.
 
Input
몇 개의 그룹 이 있 고 각 그룹의 첫 번 째 행동 두 개의 숫자 N(1<=N<=500),M 을 입력 하 십시오.그 중에서 N 은 팀 의 개 수 를 나타 내 고 M 은 이어서 M 줄 의 입력 데 이 터 를 나타 낸다.다음 M 줄 데이터 에서 줄 당 두 개의 정수 P1 이 있 는데 P2 는 P1 팀 이 P2 팀 을 이 겼 다 는 것 을 나타 낸다.
 
Output
요구 에 부합 되 는 순 위 를 제시 하 다.출력 할 때 파티 번호 사이 에 빈 칸 이 있 고,꼴찌 뒤에 빈 칸 이 없습니다.
기타 설명:조건 에 부합 되 는 순 위 는 유일한 것 이 아 닐 수 있 습 니 다.이때 출력 을 요구 할 때 번호 가 작은 팀 이 앞 에 있 습 니 다.입력 데이터 보증 은 정확 하 다.즉,입력 데 이 터 는 반드시 요구 에 부합 되 는 순 위 를 확보 하 는 것 이다.
 
Sample Input

  

   4 3
1 2
2 3
4 3
  

 
Sample Output

  

   1 2 4 3
  

 
        가장 간단 한 토폴로지 정렬 은 숫자 가 적 고 행렬 을 직접 사용한다.나중에 풀 었 던 문 제 는 행렬 로 표시 하지 못 하 는 문제 가 많 았 습 니 다.인접 표 나 링크 로 표시 해 야 합 니 다.주로 deg[i]를 0 으로 찾 았 습 니 다.그 는 바로 앞 에 서 있 었 습 니 다.그 를 시작 으로 그 와 연 결 된 점 의 deg[]-이렇게 되면 순 위 는 점수 가 우선 이 고 점수 가 같은 사전 순서대로 배열 되 었 습 니 다.이 문제 의 코드 를 먼저 붙 입 니 다.
링크:http://acm.hdu.edu.cn/showproblem.php?pid=1285
코드:

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;

const int N = 505;

int degree[N], res[N];
bool map[N][N];
vector<int> a[N];
int n, m;

void Topo()
{
    int i, j, p;
    for(i = 1; i <= n; i++)
    {
        p = -1;
        for(j = 1; j <= n; j++)
        {
            if(degree[j] == 0)
            {
                degree[j]--;
                res[i] = p = j;
                break;
            }
        }
        for(j = 1; j <= n; j++)
        {
            if(map[p][j] == true)
            {
                map[p][j] = false;
                degree[j]--;
            }
        }
    }
}

void output()
{
    int i;
    printf("%d", res[1]);
    for(i = 2; i <= n; i++)
    {
        printf(" %d", res[i]);
    }
    printf("
");
}

int main()
{
    int i, x, y;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        memset(map, false, sizeof(map));
        memset(degree, 0, sizeof(degree));
        memset(res, 0, sizeof(res));
        for(i = 1; i <= n; i++) a[i].clear();
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d", &x, &y);
            if(map[x][y] == false)
            {
                map[x][y] = true;
                degree[y]++;
            }
        }
        Topo();
        output();
    }

    return 0;
}