結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2026-02-03 11:19:16
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 625 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,806 ms
コンパイル使用メモリ 337,164 KB
実行使用メモリ 16,676 KB
最終ジャッジ日時 2026-02-03 11:19:28
合計ジャッジ時間 11,324 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 2 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9;
int n,m,cnt,a[N],vis[N],f[N];
vector<int>mp[N];
void dfs(int x)
{
	a[cnt]++;
	for(auto v:mp[x])
		if(!vis[v])
			vis[v]=1,dfs(v); 
}
int main()
{
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			vis[i]=1,cnt++,dfs(i);
	for(int i=1;i<=n;i++)f[i]=INF;
	f[0]=0;
	for(int i=1;i<=cnt;i++)
		for(int j=n;j>=a[i];j--)
			if(f[j-a[i]]!=INF)
				f[j]=min(f[j],f[j-a[i]]+1);
	for(int i=1;i<=n;i++)
		if(f[i]==INF)cout<<-1<<"\n";
		else cout<<f[i]-1<<"\n";
	return 0; 
}
0