fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout);
  3. #define TaZinh "color"
  4. using namespace std;
  5.  
  6. #define ll long long
  7. #define PB push_back
  8. #define ALL(a) a.begin(), a.end()
  9. #define REP(i, n) for(int i = 0; i < n; ++ i)
  10. #define FOR(i, a, b) for(int i = a; i <= b; ++ i)
  11. #define FOD(i, a, b) for(int i = a; i >= b; -- i)
  12.  
  13. template<class X, class Y>
  14.         bool maximize(X &x, const Y & y){
  15.                 if(x < y){
  16.                         x = y;
  17.                         return true;
  18.                 }
  19.                 else return false;
  20.         }
  21.  
  22. template<class X, class Y>
  23.         bool minimize(X &x, const Y & y){
  24.                 if(x > y){
  25.                         x = y;
  26.                         return true;
  27.                 }
  28.                 else return false;
  29.         }
  30.  
  31. const int N = 1e5 + 5;
  32. const int MOD = 1e9 + 7;
  33.  
  34. int n, m, c[N], ans, res;
  35. vector <int> g[N];
  36. bool del[N];
  37.  
  38. namespace sub1{
  39.  
  40.         void dfs(int u){
  41.                 del[u] = true; ++ ans;
  42.                 for(int v : g[u]) if(!del[v] && c[v] == c[u])
  43.                         dfs(v);
  44.         }
  45.  
  46.         void solve(void){
  47.                 FOR(i, 1, n){
  48.                         int tmp = c[i];
  49.                         FOR(j, 1, n){
  50.                                 c[i] = j;
  51.                                 FOR(k, 1, n)
  52.                                         del[k] = false;
  53.                                 ans = 0;
  54.                                 dfs(i);
  55.                                 maximize(res, ans);
  56.                         }
  57.                         c[i] = tmp;
  58.                 }
  59.                 cout << res << "\n";
  60.                 res = 0;
  61.         }
  62. }
  63.  
  64. namespace sub2{
  65.  
  66.         int kth[N], f[N], Ma[N], Rank;
  67.  
  68.         void dfs(int u){
  69.                 ++ f[Rank];
  70.                 kth[u] = Rank;
  71.                 del[u] = true;
  72.                 for(int v : g[u]) if(!del[v] && c[v] == c[u])
  73.                         dfs(v);
  74.         }
  75.  
  76.         void solve(void){
  77.  
  78.                 FOR(i, 1, n){
  79.                         del[i] = false;
  80.                         f[i] = false;
  81.                         kth[i] = 0;
  82.                 }
  83.  
  84.                 Rank = 0;
  85.  
  86.                 FOR(i, 1, n) if(!del[i]){
  87.                         ++ Rank;
  88.                         dfs(i);
  89.                         maximize(res, f[Rank]);
  90.                 }
  91.                 FOR(u, 1, n){
  92.                         for(int v : g[u]) if(kth[u] != kth[v]){
  93.                                 Ma[c[v]] = 0;
  94.                                 del[kth[v]] = 0;
  95.                         }
  96.                         for(int v : g[u]) if(kth[u] != kth[v] && !del[kth[v]]){
  97.                                 Ma[c[v]] += f[kth[v]];
  98.                                 del[kth[v]] = true;
  99.                                 maximize(res, Ma[c[v]] + 1);
  100.                         }
  101.                 }
  102.                 cout << res << "\n";
  103.                 res = 0;
  104.         }
  105. }
  106.  
  107. int main(void){
  108.  
  109.         if(fopen(TaZinh".inp", "r"))
  110.                 TSun(TaZinh);
  111.  
  112.         int Sun; cin >> Sun;
  113.         REP(love, Sun){
  114.                 cin >> n >> m;
  115.                 FOR(i, 1, n){
  116.                         cin >> c[i];
  117.                         g[i].clear();
  118.                 }
  119.                 FOR(i, 1, m){
  120.                         int u, v; cin >> u >> v;
  121.                         if(u == v) continue;
  122.                         g[u].PB(v); g[v].PB(u);
  123.                 }
  124.  
  125.                 if(n <= 100){
  126.                         sub1 :: solve();
  127.                         continue;
  128.                 }
  129.                 sub2 :: solve();
  130.         }
  131.         return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 6848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LBEKR2
language:
C++ (gcc 8.3)
created:
45 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!