Pagini recente » Istoria paginii utilizator/sharky12592 | Profil moga_florian | Profil woogiefan | Diferente pentru autumn-warmup-2007/solutii/runda-2 intre reviziile 19 si 56 | Cod sursa (job #2861143)
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define x first
#define y second
#define mod 1000000007
using namespace std;
int n, m, maxSteps, x, y;
int steps[100100];
vector < int > V[100100];
bitset < 100100 > viz;
void defaultValues() {
memset(steps, 0, sizeof(steps));
viz.reset();
}
void dfs(int x)
{
viz[x] = true;
for (auto it : V[x]) {
if (!viz[it]) {
steps[it] = steps[x] + 1;
maxSteps = max(steps[it], maxSteps);
dfs(it);
}
}
}
void runDfs() {
int node = -1;
dfs(1);
for (int i = 1; i <= n; i++) {
if (steps[i] == maxSteps) {
node = i;
break;
}
}
defaultValues();
dfs(node);
cout << "Diameter: " << 1 + maxSteps << "\n";
}
void bfs(int x) {
queue < int > Q;
Q.push(x);
viz[x] = true;
while (!Q.empty()) {
int curr = Q.front();
Q.pop();
for (auto it : V[curr]) {
if (!viz[it]) {
viz[it] = true;
steps[it] = steps[curr] + 1;
maxSteps = max(maxSteps, steps[it]);
Q.push(it);
}
}
}
}
void runBfs() {
int node = -1;
bfs(1);
for (int i = 1; i <= n; i++) {
if (steps[i] == maxSteps) {
node = i;
break;
}
}
defaultValues();
bfs(node);
cout << "Diameter: " << 1 + maxSteps << "\n";
}
int main() {
ifstream cin("darb.in");
ofstream cout("darb.out");
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
cin >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
runDfs();
// runBfs();
return 0;
}