結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー cho435
提出日時 2023-08-04 22:32:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 565 bytes
コンパイル時間 3,361 ms
コンパイル使用メモリ 257,036 KB
最終ジャッジ日時 2025-02-15 23:00:05
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
	int n,m;
	cin>>n>>m;
	vector<int> in(n,0),ou(n,0);
	atcoder::dsu uf(n);
	rep(i,m){
		int u,v;
		cin>>u>>v;
		u--; v--;
		ou.at(u)++;
		in.at(v)++;
		uf.merge(u,v);
	}
	ll ans=0;
	rep(i,n){
		if(in.at(i)>ou.at(i)) ans+=in.at(i)-ou.at(i);
	}
	map<int,int> mp;
	rep(i,n) mp[uf.leader(i)]++;
	ans-=2;
	for(auto [ld,nm]:mp){
		if(nm==1&&in.at(ld)==0){
			continue;
		}
		ans+=2;
	}
	if(ans>0) ans--;
	cout<<ans<<endl;
}
0