Indeedなう（予選B） : C - 木

問題文の読み間違いでタイムロス。
http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualc_3

問題

1～N番の頂点とN-1本の無向辺からなる木を成すグラフが与えられる。

以下の順で作られる数列を考える。

1. 頂点1を選ぶ。
2. 選択済みの頂点と隣接する点のうち、未選択の点を選ぶ、という作業を未選択の点がなくなるまで繰り返す。
3. 頂点番号を選択順に並べ数列を作る。

上記手順で生成可能な辞書順最小の数列を答えよ。

解法

辞書順最小ということは、小さな番号の頂点ほど早めに選択すると良い。
よって、選択可能な頂点（すなわち初回は1固定で、２回目以降は選択済み頂点の隣接点群）のうち、最小値の頂点を選択することを繰り返せばよい。

int N;
vector<int> E[101000];
set<int> S;
vector<int> R;
int vis[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	S.insert(0);
	while(S.size()) {
		x=*S.begin();
		S.erase(S.begin());
		if(vis[x]) continue;
		
		R.push_back(x+1);
		vis[x]=1;
		FOR(i,E[x].size()) S.insert(E[x][i]);
	}
	
	FOR(i,N) _P("%d%s",R[i], (i==N-1)?"\n":" ");
}

まとめ

最初単なるDFSかと勘違いして時間を損した。