結果

問題 No.317 辺の追加
コンテスト
ユーザー catupper
提出日時 2015-12-09 23:58:28
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 813 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 458 ms
コンパイル使用メモリ 78,524 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2026-04-04 17:47:58
合計ジャッジ時間 10,721 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 2 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

#define INF (1 << 29)

int dp[108000], dd[108000];
int mm, n, m, x, y;
int cnt[108000], res[108000];
int u[108000];

int r(int x){
	if(u[x] == x)return x;
	return u[x] = r(u[x]);
}

void unite(int x, int y){
//	if(r(x) == r(y))return;
	x = r(x);
	y = r(y);
	u[x] = y;
}

int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++)u[i] = i;
	for(int i = 0;i < m;i++){
		cin >> x >> y;
		unite(x, y);
	}
	for(int i = 1;i <= n;i++){
		cnt[r(i)]++;
	}
	fill(dp, dp + n + 3, INF);
	dp[0] = 0;
	for(int i = 1;i <= n;i++){
		if(cnt[i]){
			for(int j = n;j - cnt[i] >= 0;j--){
				dp[j] = min(dp[j], dp[j - cnt[i]] + 1);
			}
		}
	}
	for(int i = 1;i <= n;i++){
		if(dp[i] == INF)cout << -1 << endl;
		else cout << dp[i] - 1 << endl;
	}
	return 0;	
}
0