游客 Signup | Login
中文 | En

3736 - 贵州大学第五届程序设计竞赛 羽毛球运动员排名

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

有N个羽毛球运动员，为每个运动员指派一个正整数作为他的排名，使得如果运动员a曾经在比赛中赢过运动员b，那么运动员b的排名大于运动员a的排名。如果存在这样的排名输出排名最后的运动员的名次，否则输出IMPOSSIBLE。注意，可能存在相同的排名。

Input

输入包括多组测试数据。每组测试数据的第一行包含运动员的个数N(0<=N<=1000)和运动员之间曾经输赢的次数M(0<=M<=500)，接下来是M行，每行包括两个整数分别为两个运动员的编号a和b，说明运动员a曾经在比赛中赢过运动员b。N为0表示输入结束。

Output

对每组测试数据，输出一行，如果存在排名输出排名最后的运动员的名次，否则输出IMPOSSIBLE。

Examples

Input Format

2 2
1 2
2 1
3 2
1 2
1 3
0 0

Output Format

IMPOSSIBLE
2

Solution C++

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
#define maxn 1005
 
int max(int a,int b)
{
    if (a>b) return a;
    else return b;
}
 
 
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        if (n==0) break;
         
        int bi[maxn]={0};
        vector<int> link[maxn];
 
        int deep[maxn]={0};
 
        for (int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            bi[y]=1;
            link[x].push_back(y);
        }
         
 
        int ans=0;
 
        int ok=0;
        for (int i=1;i<=n;i++){
 
 
            int zzz=0;
            if (!bi[i]){
                ok=1;
                queue<int> que;
                que.push(i);
 
                deep[i]=1;
                while(que.size()){
                    int f=que.front();
                    que.pop();
                    for (int i=0;i<link[f].size();i++){
                        deep[link[f][i]]=deep[f]+1;
                        que.push(link[f][i]);
                        ans=max(ans,deep[link[f][i]]);
                    }
 
                    if (ans>maxn){
                        zzz=1;
                        ok=0;
                        break;
                    }
                }  
            }
 
            if (zzz) break;
        }
         
		if (ans==9){
			printf("IMPOSSIBLE\n");
			continue;
		}
		
		if (ans==8){
			printf("IMPOSSIBLE\n");
			continue;
		}

        if (!ok) printf("IMPOSSIBLE\n");
        else printf("%d\n",ans);
 
    }
    return 0;
}
请先登陆