fork download 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         int t = sc.nextInt();
  8.  
  9.         while (t-- > 0) {
  10.             int n = sc.nextInt();
  11.             int e = sc.nextInt();
  12.  
  13.             List<List<Integer>> adj=new ArrayList<>();
  14.             for(int i=0;i<=n;i++)
  15.             adj.add(new ArrayList<>());
  16.  
  17.  
  18.             for (int k = 0; k < e; k++) {
  19.                 int u = sc.nextInt();
  20.                 int v = sc.nextInt();
  21.                 adj.get(u).add(v);
  22.                 adj.get(v).add(u);
  23.             }
  24.  
  25.             int visited[]=new int[n+1];
  26.             int level[]=new int[n+1];
  27.             int ways[]=new int[n+1];
  28.             Queue<Integer> q=new LinkedList<>();
  29.  
  30.             q.add(1);
  31.             visited[1]=1;
  32.             level[1]=0;
  33.             ways[1]=1;
  34.  
  35.             while(!q.isEmpty())
  36.             {
  37.             	int temp=q.poll();
  38.             	System.out.print(temp+" ");
  39.             	for(int neighbour:adj.get(temp))
  40.             	{
  41.             		if(visited[neighbour]==0)
  42.             		{
  43.             			q.add(neighbour);
  44.             			visited[neighbour]=1;
  45.             			level[neighbour]=level[temp]+1;
  46.             			ways[neighbour]=ways[temp];
  47.             		}
  48.             		else
  49.             		{
  50.             			if(level[temp]+1==level[neighbour])
  51.             			ways[neighbour]+=ways[temp];
  52.             		}
  53.             	}
  54.  
  55.             }
  56.             System.out.println();
  57.  
  58.             for(int i=1;i<=n;i++)
  59.             {
  60.              System.out.println(i+" "+ways[i]);
  61.  
  62.             }
  63.  
  64.         }
  65.     }
  66. }
Success #stdin #stdout 0.2s 60908KB
comments (?)
stdin 
1
5 6
1 2
1 3
2 4
3 4
4 5
3 5
stdout 
1 2 3 4 5 
1 1
2 1
3 1
4 2
5 1
https://ideone.com/tBC1Gy
language:
Java (HotSpot 12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!