fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. public class Main {
  7.  
  8.     public static void main(String[] args) throws IOException {
  9.         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  10.         StringTokenizer tokenizer = new StringTokenizer(in.readLine());
  11.         int n = Integer.parseInt(tokenizer.nextToken());
  12.         int k = Integer.parseInt(tokenizer.nextToken());
  13.         int[] cows = new int[n + 1];
  14.         List<Integer>[] viewed = new List[n + 1];
  15.         for (int j = 1; j <= n; j++) {
  16.             cows[j] = j;
  17.             viewed[j] = new ArrayList<>();
  18.             viewed[j].add(j);
  19.         }
  20.         for (long t = 1; t <= k; t++) {
  21.             tokenizer = new StringTokenizer(in.readLine());
  22.             int a = Integer.parseInt(tokenizer.nextToken());
  23.             int b = Integer.parseInt(tokenizer.nextToken());
  24.             int c = cows[a];
  25.             int d = cows[b];
  26.             cows[a] = d;
  27.             cows[b] = c;
  28.             viewed[cows[a]].add(a);
  29.             viewed[cows[b]].add(b);
  30.         }
  31. for(int i=1;i<=n;i++)
  32. System.out.println("PHY "+cows[i]);
  33.         int[] answer = new int[n + 1];
  34.         for (int r = 1; r <= n; r++) {
  35.             if (cows[r] != 0) {
  36.                 List<Integer> cycle = new ArrayList<>();
  37.                 int j = r;
  38.                 while (cows[j] != 0) {
  39.                     cycle.add(j);
  40.                     j = cows[j];
  41.                     cows[cycle.get(cycle.size() - 1)] = 0;
  42.                 }
  43.                 Set<Integer> viewedHere = new HashSet<>();
  44.                 for (int cow : cycle) {
  45.                     viewedHere.addAll(viewed[cow]);
  46.                 }
  47.                 for (int cow : cycle) {
  48.                     answer[cow] = viewedHere.size();
  49.                 }
  50.             }
  51.         }
  52.         StringBuilder out = new StringBuilder();
  53.         for (int j = 1; j <= n; j++) {
  54.             out.append(answer[j]).append('\n');
  55.         }
  56.         System.out.print(out);
  57.     }
  58. }
Success #stdin #stdout 0.08s 48300KB
comments (?)
stdin
copy 
5 4
1 3
1 2
2 3
2 4
stdout
copy 
PHY 2
PHY 4
PHY 3
PHY 1
PHY 5
4
4
3
4
1
https://ideone.com/ZvK8bh
language:
Java (HotSpot 12)
created:
2 years 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!