제출 #863226

#제출 시각아이디문제언어결과실행 시간메모리
863226TAhmed33Cijanobakterije (COCI21_cijanobakterije)C++98
12 / 70
61 ms16780 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;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos);
		if (1 + dp[j][1] > mx1) {
			mx2 = mx1; mx1 = 1 + dp[j][1];
		} else if (1 + dp[j][1] > mx2) {
			mx2 = 1 + dp[j][1];
		}
	}	
	dp[pos][0] = mx1 + mx2;
	dp[pos][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 += 1 + 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...