제출 #863230

#제출 시각아이디문제언어결과실행 시간메모리
863230TAhmed33Cijanobakterije (COCI21_cijanobakterije)C++98
70 / 70
58 ms16076 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
vector <int> adj[MAXN];
int dp[MAXN][2];
bool vis[MAXN];
void dfs (int pos, int par) {
	vis[pos] = 1;
	int mx1 = 0, mx2 = 0, mx3 = 0;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos);
		if (1 + dp[j][1] > mx1) {
			mx2 = mx1; mx1 = dp[j][1];
		} else if (dp[j][1] > mx2) {
			mx2 = dp[j][1];
		}
		mx3 = max(mx3, dp[j][0]);
	}	
	dp[pos][0] = max(1 + mx1 + mx2, mx3);
	dp[pos][1] = 1 + mx1;
}
int main () {
	int mx = 0;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs(i, -1);
			mx += dp[i][0]; 
		}
	}
	cout << mx << '\n';
}
#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...