提出 #70095904

---

ソースコード 拡げる

// Problem: C - Bipartize
// Contest: AtCoder - Panasonic Programming Contest 2025（AtCoder Beginner Contest 427）
// URL: https://atcoder.jp/contests/abc427/tasks/abc427_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll tttt=1;
	//cin>>tttt;
	while(tttt--)
	{
		ll n,m;
		cin>>n>>m;
		vector<vector<ll>>G(n+7);
		while(m--)
		{
			ll u,v;
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		ll ans=4e18;
		for(int i=1;i<=n;i++)
		{
			vector<ll>col(n+7,-1);
			ll cnt=0;
			col[i]=0;
			queue<ll>q;
			q.push(i);
			while(!q.empty())
			{
				ll u=q.front();
				//cout<<u<<' ';
				q.pop();
				for(auto v:G[u])
				{
					if(col[v]!=1-col[u]&&col[v]!=-1)
					{
						cnt++;
						//cout<<u<<' '<<v<<'\n';
						continue;
					}
					if(col[v]==-1)q.push(v);
					col[v]=1-col[u];
					
				}
				//cout<<cnt<<'\n';
			}
			ans=min(ans,cnt);
			//cout<<'\n';
		}
		cout<<ans/2<<'\n';
	}
	return 0;
}

提出情報

ジャッジ結果