結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2024-06-15 12:23:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 795 bytes |
コンパイル時間 | 1,741 ms |
コンパイル使用メモリ | 178,912 KB |
実行使用メモリ | 11,216 KB |
最終ジャッジ日時 | 2024-11-14 12:26:03 |
合計ジャッジ時間 | 3,660 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define rep(i,m,n) for(int i=m; i<n; ++i)#define repl(i,m,n) for(ll i=m; i<n; ++i)vector<vector<int>> Graph;vector<bool> visited;void dfs(int v, int &cnt){visited[v] = true;cnt++;for(int nv : Graph[v]){if(visited[nv]) continue;dfs(nv, cnt);}}int main(){int N, M;cin >> N >> M;Graph.resize(2*N);rep(i, 0, M){int A, B;cin >> A >> B;Graph[A-1].push_back(B-1);Graph[B-1].push_back(A-1);}visited.assign(2*N, false);int cnt = 0, ans = N;for(int i = 0; i < 2*N; ++i){if(visited[i]) continue;dfs(i, cnt);ans -= cnt / 2;cnt = 0;}cout << ans << endl;return 0;}