#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5, mod = 1e9 + 7;
int vis[N], vid;
vector<int> adj[N];
int n, m;
pair<int, int> dfs(int u)
{
vis[u] = vid;
int node = u, ret = 0;
for (auto v : adj[u])
{
if (vis[v] != vid)
{
pair<int, int> tmp = dfs(v);
if (tmp.first > ret)
ret = tmp.first, node = tmp.second;
}
}
return {ret + 1, node};
}
int dia(int x)
{
vid++;
x = dfs(x).second;
vid++;
return dfs(x).first;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
int ret = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
ret += dia(i);
cout << ret << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3420 KB |
Output is correct |
2 |
Correct |
9 ms |
4400 KB |
Output is correct |
3 |
Correct |
13 ms |
5128 KB |
Output is correct |
4 |
Correct |
16 ms |
5980 KB |
Output is correct |
5 |
Correct |
21 ms |
6740 KB |
Output is correct |
6 |
Correct |
24 ms |
7516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
12124 KB |
Output is correct |
2 |
Correct |
4 ms |
3160 KB |
Output is correct |
3 |
Correct |
4 ms |
3676 KB |
Output is correct |
4 |
Correct |
7 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
3 ms |
3268 KB |
Output is correct |
6 |
Correct |
5 ms |
4096 KB |
Output is correct |
7 |
Correct |
7 ms |
4640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3420 KB |
Output is correct |
2 |
Correct |
9 ms |
4400 KB |
Output is correct |
3 |
Correct |
13 ms |
5128 KB |
Output is correct |
4 |
Correct |
16 ms |
5980 KB |
Output is correct |
5 |
Correct |
21 ms |
6740 KB |
Output is correct |
6 |
Correct |
24 ms |
7516 KB |
Output is correct |
7 |
Correct |
27 ms |
12124 KB |
Output is correct |
8 |
Correct |
4 ms |
3160 KB |
Output is correct |
9 |
Correct |
4 ms |
3676 KB |
Output is correct |
10 |
Correct |
7 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
2652 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
3 ms |
3268 KB |
Output is correct |
16 |
Correct |
5 ms |
4096 KB |
Output is correct |
17 |
Correct |
7 ms |
4640 KB |
Output is correct |
18 |
Correct |
1 ms |
2652 KB |
Output is correct |
19 |
Correct |
1 ms |
2652 KB |
Output is correct |
20 |
Correct |
1 ms |
2652 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
1 ms |
2652 KB |
Output is correct |
23 |
Correct |
1 ms |
2652 KB |
Output is correct |
24 |
Correct |
1 ms |
2652 KB |
Output is correct |
25 |
Correct |
1 ms |
2652 KB |
Output is correct |
26 |
Correct |
1 ms |
2652 KB |
Output is correct |
27 |
Correct |
1 ms |
2652 KB |
Output is correct |
28 |
Correct |
1 ms |
2652 KB |
Output is correct |
29 |
Correct |
29 ms |
7544 KB |
Output is correct |
30 |
Correct |
6 ms |
4188 KB |
Output is correct |
31 |
Correct |
25 ms |
7092 KB |
Output is correct |
32 |
Correct |
11 ms |
4956 KB |
Output is correct |
33 |
Correct |
21 ms |
7372 KB |
Output is correct |
34 |
Correct |
17 ms |
5764 KB |
Output is correct |
35 |
Correct |
18 ms |
7004 KB |
Output is correct |
36 |
Correct |
25 ms |
6232 KB |
Output is correct |
37 |
Correct |
21 ms |
7224 KB |
Output is correct |
38 |
Correct |
23 ms |
6748 KB |
Output is correct |
39 |
Correct |
19 ms |
7004 KB |
Output is correct |