結果

問題 No.317 辺の追加
ユーザー catuppercatupper
提出日時 2015-12-09 23:58:28
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 813 bytes
コンパイル時間 550 ms
コンパイル使用メモリ 60,000 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-15 06:04:42
合計ジャッジ時間 7,956 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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