This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
using vi = vector<int>;
using ll = long long;
#define sz(x) int(x.size())
const int mx = 100'000;
vi edge[1+mx];
int n, m;
int res = 0;
vi visit(1+mx, 0);
vector< pair<int, int> > V; //dist, node
void dfs(int u, int d)
{
// cerr << "dfs " << u << ' ' << d << '\n';
V.push_back({-d, u});
visit[u] = 1;
for(int v: edge[u])
{
if(visit[v]) continue;
dfs(v, d+1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int j = 1; j <= m; j++)
{
int a, b;
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
for(int i = 1; i <= n; i++)
{
if(visit[i]) continue;
// cerr << "component = " << i << '\n';
dfs(i, 0);
sort(V.begin(), V.end());
for(auto y: V) visit[y.second] = 0;
int src = V[0].second;
V.clear();
// cerr << "cleared\n";
dfs(src, 0);
sort(V.begin(), V.end());
res -= V[0].first - 1;
V.clear();
}
cout << res << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |