fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Spoj
  5. {
  6.     public static void main(String args[])throws Exception
  7.     {
  8.         BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
  9.         StringBuilder sb=new StringBuilder();
  10.         int t=Integer.parseInt(bu.readLine()),cs=1;
  11.         while(t-->0)
  12.         {
  13.             sb.append("Scenario #"+cs+++":\n");
  14.             StringTokenizer st=new StringTokenizer(bu.readLine());
  15.             int n=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken()),i;
  16.             ArrayList<Integer> g[]=new ArrayList[n];
  17.             boolean vis[]=new boolean[n]; int deg[]=new int[n];
  18.             for(i=0;i<n;i++)
  19.             g[i]=new ArrayList<>();
  20.             for(i=0;i<r;i++)
  21.             {
  22.                 st=new StringTokenizer(bu.readLine());
  23.                 int l=Integer.parseInt(st.nextToken()),f=Integer.parseInt(st.nextToken());
  24.                 g[f].add(l);
  25.                 deg[l]++;
  26.             }
  27.  
  28.             Queue<Pair> q=new LinkedList<>();
  29.             ArrayList<Pair> ans=new ArrayList<>();
  30.             for(i=0;i<n;i++)
  31.             if(deg[i]==0)
  32.             {
  33.                 vis[i]=true;
  34.                 q.add(new Pair(i,1));
  35.             }
  36.  
  37.             while(!q.isEmpty())
  38.             {
  39.                 Pair p=q.poll();
  40.                 ans.add(p);
  41.                 for(i=0;i<g[p.x].size();i++)
  42.                 if(!vis[g[p.x].get(i)])
  43.                 {
  44.                     deg[g[p.x].get(i)]--;
  45.                     if(deg[g[p.x].get(i)]==0)
  46.                     {
  47.                         vis[g[p.x].get(i)]=true;
  48.                         q.add(new Pair(g[p.x].get(i),p.y+1));
  49.                     }
  50.                 }
  51.             }
  52.  
  53.             Collections.sort(ans, new Comparator<Pair>() {
  54.                 public int compare(Pair o1, Pair o2) {
  55.                     if(o1.y>o2.y) return 1;
  56.                     else if(o1.y==o2.y) return o1.x>o2.x?1:-1;
  57.                     else return -1;
  58.                 }});
  59.  
  60.             for(i=0;i<ans.size();i++)
  61.             sb.append(ans.get(i).y+" "+ans.get(i).x+"\n");
  62.         }
  63.         System.out.print(sb);
  64.     }
  65.  
  66.     static class Pair
  67.     {
  68.         int x,y;
  69.         Pair(int a,int b)
  70.         {
  71.             x=a; y=b;
  72.         }
  73.     }
  74. }
  75.  
Success #stdin #stdout 0.11s 36472KB
comments (?)
stdin
copy 
2
5 6
2 0
2 4
1 4
1 2
3 2
4 0
5 4
1 0
2 0
3 2
4 2
stdout
copy 
Scenario #1:
1 0
2 4
3 2
4 1
4 3
Scenario #2:
1 0
2 1
2 2
3 3
3 4
https://ideone.com/l9tEzU
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
secret

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!