結果

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

ソースコード

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);
	}
	map<int,int> mp;
	rep(i,n){
		if(in.at(i)>ou.at(i)) mp[uf.leader(i)]+=in.at(i)-ou.at(i);
		mp[uf.leader(i)];
	}
	ll ans=0;
	for(auto [ld,nm]:mp){
		if(in.at(ld)==0&&ou.at(ld)==0){
			continue;
		}
		if(nm>0) ans+=nm-1;
		ans++;
	}
	if(ans>0) ans--;
	cout<<ans<<endl;
}
0