Length of the Longest Connected Path

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	maroonrk	152

Can someone explain how to find the length of the longest connected path in a graph. I have tried using the common technique, of finding the most distant node(leaf node) from any node and then find the most distant node from this leaf node using dfs twice. This is my code, don't know why this is giving RE.

Code

vector <vector > adj; int visit[N] = {0}; int dist[N] = {0}; int lf; void dfs1(int u, int d) { visit[u] = 1; dist[u] = d;

if (dist[u] > dist[lf])
    lf = u;

for (int i = 0; i < (int)adj[u].size(); ++i) {
    int e = adj[u][i];
    if (visit[e] == 0)
       dfs1(e, d + 1);
}

} void dfs(int start, int d) { visit[start] = 2; dist[start] = d; for (int i = 0; i < (int)adj[start].size(); ++i) { int t = adj[start][i]; if (visit[t] < 2) { dfs(t, d + 1); } } }

void solve() { int n, m, f; cin >> n; m = n — 1; adj = vector <vector > (n); for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); --u; --v; adj[u].push_back(v); adj[v].push_back(u); }

memset(dist, 0, sizeof dist);
int ans = 0;
for (int i = 0; i < n; ++i) {
    if (visit[i] > 0)
       continue;
    lf = i;
    dfs1(i, 0);
    dfs(lf, 0);         
}

for (int i = 0; i < n; ++i) {
    ans = max (ans, dist[i]);
}
// cout << ans << " ";
printf ("%d", ans);

}

[problem:Problem] https://www.spoj.com/problems/PT07Z/

Блог пользователя AaZaDi