Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.Stack;
- import java.util.LinkedList;
- import java.util.Queue;
- class GraphNode<E> {
- private int index;
- private E info;
- private LinkedList<GraphNode<E>> neighbors;
- public GraphNode(int index, E info) {
- this.index = index;
- this.info = info;
- neighbors = new LinkedList<GraphNode<E>>();
- }
- boolean containsNeighbor(GraphNode<E> o){
- return neighbors.contains(o);
- }
- void addNeighbor(GraphNode<E> o){
- neighbors.add(o);
- }
- void removeNeighbor(GraphNode<E> o){
- if(neighbors.contains(o))
- neighbors.remove(o);
- }
- @Override
- public String toString() {
- String ret= "INFO:"+info+" SOSEDI:";
- for(int i=0;i<neighbors.size();i++)
- ret+=neighbors.get(i).info+" ";
- return ret;
- }
- @Override
- public boolean equals(Object obj) {
- @SuppressWarnings("unchecked")
- GraphNode<E> pom = (GraphNode<E>)obj;
- return (pom.info.equals(this.info));
- }
- public int getIndex() {
- return index;
- }
- public void setIndex(int index) {
- this.index = index;
- }
- public E getInfo() {
- return info;
- }
- public void setInfo(E info) {
- this.info = info;
- }
- public LinkedList<GraphNode<E>> getNeighbors() {
- return neighbors;
- }
- public void setNeighbors(LinkedList<GraphNode<E>> neighbors) {
- this.neighbors = neighbors;
- }
- }
- class Graph<E> {
- int num_nodes;
- GraphNode<E> adjList[];
- @SuppressWarnings("unchecked")
- public Graph(int num_nodes, E[] list) {
- this.num_nodes = num_nodes;
- adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- adjList[i] = new GraphNode<E>(i, list[i]);
- }
- @SuppressWarnings("unchecked")
- public Graph(int num_nodes) {
- this.num_nodes = num_nodes;
- adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
- }
- public void setNodeAt(int i,E a)
- {
- adjList[i].setInfo(a);
- }
- int adjacent(int x, int y) {
- return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
- }
- void addEdge(int x, int y) {
- if (!adjList[x].containsNeighbor(adjList[y])) {
- adjList[x].addNeighbor(adjList[y]);
- }
- }
- void deleteEdge(int x, int y) {
- adjList[x].removeNeighbor(adjList[y]);
- }
- int izmini(int start,int find,int n)
- {
- if(start==find)
- return n-1;
- LinkedList<GraphNode<E>> sosedi= adjList[start].getNeighbors();
- if(n>num_nodes-1)
- return 1000;
- if(sosedi.contains(adjList[find]))
- return n;
- int min=10000;
- int br;
- for(int i=0;i<sosedi.size();i++)
- {
- int index=sosedi.get(i).getIndex();
- if(index!=start)
- {
- br = izmini(index,find,n+1);
- if(br<min)
- min=br;
- }
- }
- return min;
- }
- void dfsSearch(int node) {
- boolean visited[] = new boolean[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- visited[i] = false;
- dfsRecursive(node, visited);
- }
- void dfsRecursive(int node, boolean visited[]) {
- visited[node] = true;
- System.out.println(node + ": " + adjList[node].getInfo());
- for (int i = 0; i < adjList[node].getNeighbors().size(); i++) {
- GraphNode<E> pom = adjList[node].getNeighbors().get(i);
- if (!visited[pom.getIndex()])
- dfsRecursive(pom.getIndex(), visited);
- }
- }
- void dfsNonrecursive(int node) {
- boolean visited[] = new boolean[num_nodes];
- for (int i = 0; i < num_nodes; i++)
- visited[i] = false;
- visited[node] = true;
- System.out.println(node+": " + adjList[node].getInfo());
- Stack<Integer> s = new Stack<Integer>();
- s.push(node);
- GraphNode<E> pom;
- while (!s.isEmpty()) {
- pom = adjList[s.peek()];
- GraphNode<E> tmp=null;
- for (int i = 0; i < pom.getNeighbors().size(); i++) {
- tmp = pom.getNeighbors().get(i);
- if (!visited[tmp.getIndex()])
- break;
- }
- if(tmp!=null&&!visited[tmp.getIndex()]){
- visited[tmp.getIndex()] = true;
- System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
- s.push(tmp.getIndex());
- } else s.pop();
- }
- }
- @Override
- public String toString() {
- String ret = new String();
- for (int i = 0; i < this.num_nodes; i++)
- ret += i + ": " + adjList[i] + "\n";
- return ret;
- }
- }
- public class CountFacebookFriends {
- public static void main(String args[]) throws NumberFormatException, IOException{
- BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
- int N=Integer.parseInt(bf.readLine());
- String [] d=new String[N];
- Graph<String> facebook=new Graph<String>(N,d);
- for(int i=0;i<N;i++)
- {
- int n=Integer.parseInt(bf.readLine());
- for(int j=0;j<n;j++)
- {
- String s=bf.readLine();
- String [] parts=s.split(" ");
- int index=Integer.parseInt(parts[0]);
- facebook.addEdge(i, index);
- facebook.setNodeAt(index, parts[1]+" "+parts[2]);
- }
- }
- int from=Integer.parseInt(bf.readLine());
- int to=Integer.parseInt(bf.readLine());
- System.out.println(facebook.izmini(from, to, 1));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement