제출 #529018

#제출 시각아이디문제언어결과실행 시간메모리
529018penguinhackerCijanobakterije (COCI21_cijanobakterije)C++14
70 / 70
37 ms13232 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m;
vector<int> adj[mxN];
bool vis[mxN];

ar<int, 2> dfs(int u) {
	vis[u]=1;
	ar<int, 2> d={};
	int diam=0;
	for (int v : adj[u])
		if (!vis[v]) {
			ar<int, 2> x=dfs(v);
			diam=max(diam, x[0]);
			if (x[1]+1>d[0]) {
				swap(d[0], d[1]);
				d[0]=x[1]+1;
			} else if (x[1]+1>d[1])
				d[1]=x[1]+1;
		}
	diam=max(diam, d[0]+d[1]);
	return {diam, d[0]};
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int ans=0;
	for (int i=0; i<n; ++i)
		if (!vis[i])
			ans+=dfs(i)[0]+1;
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...