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.         int[] answer = new int[n + 1];
  32.         for (int r = 1; r <= n; r++) {
  33.             if (cows[r] != 0) {
  34.                 List<Integer> cycle = new ArrayList<>();
  35.                 int j = r;
  36.                 while (cows[j] != 0) {
  37.                     cycle.add(j);
  38.                     j = cows[j];
  39.                     cows[cycle.get(cycle.size() - 1)] = 0;
  40.                 }
  41.                 Set<Integer> viewedHere = new HashSet<>();
  42.                 for (int cow : cycle) {
  43.                     viewedHere.addAll(viewed[cow]);
  44.                 }
  45.                 for (int cow : cycle) {
  46.                     answer[cow] = viewedHere.size();
  47.                 }
  48.             }
  49.         }
  50.         StringBuilder out = new StringBuilder();
  51.         for (int j = 1; j <= n; j++) {
  52.             out.append(answer[j]).append('\n');
  53.         }
  54.         System.out.print(out);
  55.     }
  56. }
Success #stdin #stdout 0.07s 47252KB
comments (?)
stdin
copy 
5 4
1 3
1 2
2 3
2 4
stdout
copy 
4
4
3
4
1
https://ideone.com/bPUHdB
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!