NOJ 2015 섬서성 프로그래밍 경연대회 인터넷 예선(정식경기)(바쁜 수강신청 시스템 - 토폴로지 정렬 주의중변)

D - 바쁜 수강신청 시스템

Time Limit: 10000 ms        Memory Limit: 65536 KB

Submit

Description

학기 말마다 모든 사람들이 주목하는 수강신청 시간이다. 인원수가 너무 많아서 모 학교의 서버는 무수한 학생들에 의해 자주 폭발한다. 이것은 교무 시스템 어른들이 너희들이 수강신청을 이렇게 느리게 하는데 뜻밖에도 우리를 탓한다고 말한다.그래서 매번 교무 시스템은 서버가 마비되기 전에 닫는다.수많은 학생들의 강렬한 항의에 교무 시스템은 타협하여 모두에게 다시 한 번 기회를 주었지만, 그는 우리에게 가장 빠른 방식으로 선택한 과정을 결정하고 선택한 후에 물러나라고 했다.
이것은 대학 1학년부터 4학년까지의 임의의 과정을 선택할 수 있고 심지어는 자신의 전공이 아닐 수도 있다.그러나 이것은 많은 새로운 문제를 일으킬 것이다. 만약에 내가 고등수학에 들어가기 전에 회로 분석 기초를 전공했다면 찌꺼기를 배우면 과목을 졸업할 수 있지만 아무도 과목을 졸업하기를 원하지 않을 것이다.
찌꺼기는 다음 학기에 적어도 N과목을 들어야 한다. 그렇지 않으면 찌꺼기는 정상적으로 진학할 수 없을 것이다.
가령 학교가 매 과목을 다 마친 후에야 다른 과목을 듣는다고 가정하면, 찌꺼기는 그가 다음 학기에 과목을 마칠 수 있을지 궁금하다.가령 학업 찌꺼기는 정상적인 과목 순서에 따라 과목을 등록하지 않을 것이다.
배움의 찌꺼기가 다시 어려워져서 학패에게 물어볼 수밖에 없었다. 결국 애수의 학패는 한 번 보고 결론을 내렸다. 역시 학패다.
학패는 특히 쇼를 좋아해서 한 번 본 후에
만약 찌꺼기를 배워서 과목을 그만두면, 그는 "You will fail some exam, but I think I can deal with it"라고 말할 것이다.
만약 학업 찌꺼기가 졸업하지 않고 단지 하나의 과정 안배만 있다면, 그는 "I've got it by using my IQ and RP."라고 말할 것이다.
만약 여러 가지 안배 방식이 있다면, 학패는 "It's too easy. I've found many solutions in my first glance"라고 말할 것이다.
 

Input

입력 데이터는 여러 줄을 포함하고 첫 번째 줄은 N, K(0≤N≤1500, 2≤K≤1500)를 제시한다. 다음 학기에 N과목을 듣게 된다는 뜻이다. 다음 K과목에서는 한 줄당 적어도 두 개의 수가 있고, 첫 번째 숫자는 과목 A의 번호(A≤N)를 나타내며, 그 후의 모든 숫자는 B의 과목 번호를 대표한다. 그리고 과목 B가 끝난 후에야 비로소 과목 A를 알아들을 수 있다. 이 K과목에서는 한 줄이 0으로 끝난다.0은 어떤 과정의 과정 번호도 되지 않습니다.
입력은 EOF로 끝납니다.
 

Output

모든 결과에 대해 출력학패가 말하고자 한다면 답이 유일하다면 다음 줄에서 이 답안을 출력하세요.

Sample Input

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

Sample Output

I've got it by using my IQ and RP.
4 3 2 1

Hint

-
토폴로지 정렬, 모서리 바꾸기 주의

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (1500+100) 
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}


int k;
const char s1[]="You will fail some exam ,but I think I can deal with it.
";
const char s2[]="I've got it by using my IQ and RP.
";
const char s3[]="It's too easy.I've found many solutions in my first glance.
";

int n,indegree[MAXN];
int f[MAXN][MAXN];
bool b[MAXN];
int q[MAXN*4];
void topsort()    
{    
    int head_=1,tail=0;
	int fl=0,flm=0;    
    Fork(i,1,n)  
        if (indegree[i]==0)     
        {    
            q[++tail]=i;b[i]=1; ++fl;    
        }    
    if (fl>1) flm=1;
    
    while (head_<=tail)    
    {    
    	fl=0;
        int now=q[head_];    
        Fork(v,1,n)  
            while (f[now][v])  
            {    
                indegree[v]--;f[now][v]--;    
                if (indegree[v]==0)    
                {    
                    q[++tail]=v;b[v]=1; ++fl;    
                }                                       
            }       
        head_++;    
        
		if (fl>1) flm=1;
            
            
    }         
    if (tail==n)   
    {
    	if (flm) printf("%s",s3); 
    	
	    else 
		{
			printf("%s",s2); 
			printf("%d",q[1]);
			Fork(i,2,n) printf(" %d",q[i]);
			printf("
");  
    
		}
	}
	else printf("%s",s1);  
      
}    

int main()
{
//	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);
	
	
	while(scanf("%d%d",&n,&k)==2)
	{
		MEM(f) MEM(indegree) MEM(q) MEM(b)
		For(i,k)
		{
			int p,p2;
			scanf("%d",&p);
			while(scanf("%d",&p2)==1)
			{
				if (f[p2][p]) continue; 
				if (p2) f[p2][p]++,indegree[p]++;
				else break;
			}
		}	
		
		topsort();
			
	}
	return 0;
}