AiSD Longest path in a tree


import java.util.*;
import java.io.*;

class LongestPath {

public static void main(String[] args) throws Exception {

int n = p.nextInt();
graph = new Graph(n + 1);

for(int i = 1; i < n; i++) {
int a = p.nextInt();
int b = p.nextInt();
graph.addEdge(a, b);
}

DFS dfs = new DFS(graph);
out.println(dfs.path);
out.flush();

}

static ParserDFS p = new ParserDFS(System.in);
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static Graph graph;
}

class DFS {
DFS(Graph graph) {
this.graph = graph;

visited = new boolean[graph.V];
dfs(graph.V - 1);

visited = new boolean[graph.V];
path = 0;
dfs(last);
}

private void dfs(int v) { for(int w: graph.connected(v)) dfs(w, 1); }

private void dfs(int v, int dist) {
visited[v] = true;
if(path < dist) {
last = v;
path = dist;
}

for(int w: graph.connected(v))
if(!visited[w])
dfs(w, dist + 1);

}

Graph graph;
int last, path;
boolean[] visited;
}


class Graph {
public Graph(int V) {
this.V = V;

connected = new ArrayList[V];
for(int v = 1; v < V; v++)
connected[v] = new ArrayList();
}

public void addEdge(int v, int w) {
connected[v].add(w);
connected[w].add(v);
}

public ArrayList connected(int v) { return connected[v]; }

final int V;
private ArrayList[] connected;
}

class ParserDFS {
final private int BUFFER_SIZE = 1 << 24;

private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
char[] buf = new char[1];

public ParserDFS(InputStream in) {
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}

public int nextInt() throws Exception {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = c == '-';
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg)
return -ret;
return ret;
}

public String nextString() throws Exception {
int cnt = 0;
byte c = read();
while (c <= ' ')
c = read();
while (c > ' ') {
buf[cnt++] = (char) c;
c = read();
}
return String.valueOf(buf, 0, cnt);
}

private void fillBuffer() throws Exception {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}

public boolean hasNext() throws Exception {
byte c;
do {
c = read();
if (c == -1) {
bufferPointer--;
return false;
}
} while (c <= ' ');
bufferPointer--;
return true;
}

private byte read() throws Exception {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
}

Wyszukiwarka

Podobne podstrony:
The Man in the Tree
Building the Tree of Life In the Aura
Tommie Eriksson Tree Cults in Northern Magic
E in T?atures & nescessity
Functional Origins of Religious Concepts Ontological and Strategic Selection in Evolved Minds
You maybe in love Blue Cafe
In the?rn
Ghost in the Shell 2 0 (2008) [720p,BluRay,x264,DTS ES] THORA
Steve Fearson Card in Ceiling
E 22 Of Domine in auxilium
Assembly of outer membrane proteins in bacteria nad mitochondria

więcej podobnych podstron