JOI2007本選 問題4＠C++

しかしsol_checkが動かないので正答か確認できない

いや、Windows台なら動くかもしれないんだけどさ・・・・・・・・

まあどちらにせよ、cygwin1.dllはバージョンによって互換性がないらしいので、ソースがあったほうがいいのは確か。

ということでJOIのinfoにメール送っておいた。

内容はトポロジカルソート。合宿でやったので覚えてる。

まだこのソースで正しいと決まったわけではないので注意。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

void topological_visit(int n, vector<vector<signed char> > &table, vector<bool> &flags, vector<int> &dest, int at)
{
	flags[at] = true;
	for(int i=0;i<n;i++) {
		if(!flags[i] && table[at][i] == -1) {
			topological_visit(n, table, flags, dest, i);
		}
	}
	dest.push_back(at);
}

int main(int argc, char *argv[], char *envp[])
{
	#ifdef DEBUG
	FILE *in = stdin;
	FILE *out = stdout;
	#else
	FILE *in = fopen("input.txt", "r");
	FILE *out = fopen("output.txt", "w");
	#endif
	int n;
	int m;
	fscanf(in, "%d\n", &n);
	fscanf(in, "%d\n", &m);
	//printf("sizeof(signed char)==%d, sizeof(bool)==%d, sizeof(int)==%d\n", sizeof(signed char), sizeof(bool), sizeof(int));
	vector<vector<signed char> > table(n, vector<signed char>(n));
	for(int i=0;i<m;i++) {
		int a;
		int b;
		fscanf(in, "%d %d\n", &a, &b);
		a--;
		b--;
		table[a][b] = 1;
		table[b][a] = -1;
	}
	vector<bool> flags(n);
	vector<int> dest;
	for(int i=0;i<n;i++) {
		if(!flags[i]) {
			topological_visit(n, table, flags, dest, i);
		}
	}
	bool single_answer_flag = true;
	for(unsigned int i=0;i<dest.size();i++) {
		fprintf(out, "%d\n", dest[i]+1);
		if(i+1 < dest.size() && table[dest[i]][dest[i+1]] == 0) {
			single_answer_flag = false;
		}
	}
	fprintf(out, "%d\n", !single_answer_flag);
	fclose(in);
	fclose(out);
	return 0;
}