第7回日本情報オリンピック 春合宿 1日目 問題2 「色紙」 (Sheet)

解法：トポロジカルソート

過去の自分のほうが頭いい気がする。↓

第7回日本情報オリンピック 春合宿 1日目 「色紙」 - intさわだんのBlack History

#include <bits/stdc++.h>

using namespace std;

int n,w,h;
int d[103][103];
bool used[1003];
int ha[1004][4];
int ss[5] = {10001,10001,-1,-1};
int ans[1003];
int co;

void dfs(int x){
	used[x] = true;
	for(int i = ha[x][1];i <= ha[x][3];i++){
		for(int j = ha[x][0];j <= ha[x][2];j++){
			if(used[d[i][j]] == false)dfs(d[i][j]);
		}
	}
	ans[co++] = x;
	return;
}


int main(){
	used[0] = true;
	scanf("%d%d%d",&n,&w,&h);
	for(int i = 1;i <= n;i++){
		used[i] = false;
		for(int j = 0;j < 4;j++){
			ha[i][j] = ss[j];
		}
	}
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			int a;
			scanf("%d",&a);
			d[i][j] = a;
			ha[a][0] = min(ha[a][0],j);
			ha[a][1] = min(ha[a][1],i);
			ha[a][2] = max(ha[a][2],j);
			ha[a][3] = max(ha[a][3],i);
		}
	}
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			if(used[d[i][j]] == false)dfs(d[i][j]);
		}
	}
	for(int i = 1;i <= n;i++){
		if(used[i] == false)printf("%d ",i);
	}
	for(int i = co-1;i >= 0;i--){
		if(i == 0){
			printf("%d",ans[i]);
		}else{
			printf("%d ",ans[i]);
		}
	}

	printf("\n");
	return 0;
}