Untitled

 avatar
unknown
java
3 years ago
1.9 kB
4
Indexable
import java.io.*;
import java.util.*;

public class equalizing_money {
  static int N = 1005;
  static int[] bal = new int[N];
  static boolean[] vis = new boolean[N];
  static int sz, tot;
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int T = input.nextInt();
    for (int t = 1; t <= T; ++t) {
      int n = input.nextInt();
      int m = input.nextInt();
      int need = 0;
      for (int i = 1; i <= n; ++i) {
        bal[i] = input.nextInt();
        vis[i] = false;
        need += bal[i];
      }
      System.out.printf("Case %d: ", t);
      if (n == 0) tle();
      if (need % n != 0) {
        System.out.println("No");
      } else {
        Graph G = new Graph(n);
        for (int i = 0; i < m; ++i) {
          int u = input.nextInt();
          int v = input.nextInt();
          G.add(u, v);
        }
        need /= n;
        boolean ye = true;
        for (int i = 1; i <= n; ++i) {
          if (!vis[i]) {
            sz = 0; tot = 0;
            G.dfs(i);
            if (tot % sz != 0) {
              ye = false;
              break;
            } else {
              if (need != tot / sz) {
                ye = false;
                break;
              }
            }
          }
        }
        System.out.println(ye ? "Yes" : "No");
      }
    }
  }
  static class Graph {
    private final int n;
    private final LinkedList<Integer>[] adj;
    public Graph(int _n) {
      n = _n + 2;
      adj = new LinkedList[N];
      for (int i = 0; i < N; ++i) {
        adj[i] = new LinkedList<>();
      }
    }
    void add(int u, int v) {
      adj[u].add(v);
      adj[v].add(u);
    }
    void dfs(int v) {
      ++sz;
      tot += bal[v];
      vis[v] = true;
      for (int u : adj[v]) {
        if (!vis[u]) {
          dfs(u);
        }
      }
    }
  }
}
Editor is loading...