第7回日本情報オリンピック 春合宿 1日目 「色紙」

トポロジカルソートやるだけ。
JOI本選過去問の「最悪の記者」に類似している。→リンク

bool used[1002];//使ったかどうか
int n,w,h;
int s[1002][4];//0,1:左上、2,3:右下
int ans[1002];//答え逆順
int m[102][102];//map
int inn[4] = {100,100,0,0};
int co = 0;
void func(int x){
	for(int i = s[x][1];i <= s[x][3];i++){
		for(int j = s[x][0];j <= s[x][2];j++){
			int mm = m[i][j];
			if(mm != 0 && mm != x && used[mm] == false) func(mm);
		}
	}
	ans[co++] = x;
	used[x] = true;
	return;
}
int main(){
	memset(used,0,sizeof(used));

	scanf("%d%d%d",&n,&w,&h);
	for(int i = 0;i <= n;i++){
		for(int j = 0;j < 4;j++)s[i][j] = inn[j];
	}
	for(int i = 0;i < h;i++){
		for(int j = 0;j < w;j++){
			scanf("%d",&m[i][j]);
			int tmp = m[i][j];
			s[tmp][0] = min(j,s[tmp][0]);
			s[tmp][1] = min(i,s[tmp][1]);
			s[tmp][2] = max(j,s[tmp][2]);
			s[tmp][3] = max(i,s[tmp][3]);
		}
	}

	for(int i = 1;i <= n;i++){
		if(used[i] == true)continue;
		func(i);
	}

	for(int i = n-1;i >= 0;i--){
		if(i == 0) printf("%d\n",ans[i]);
		else printf("%d ",ans[i]);
	}

	return 0;
}