fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned ll
  7. #define ld long double
  8. typedef vector<int> vi;
  9. typedef multiset<int> mi;
  10. typedef multiset<ll> mll;
  11. typedef vector<ll> vll;
  12. typedef vector<bool> vb;
  13. typedef vector<string> vs;
  14. typedef set<ll> sll;
  15. typedef vector<vector<int>> _2vi;
  16. typedef vector<vector<ll>> _2vll;
  17. #define all(v) ((v).begin()), ((v).end())
  18. #define sz(v) ((ll)((v).size()))
  19.  
  20. #define vinp(v, n)                \
  21.     for (ull i = 0; i < (n); i++) \
  22.     cin >> (v)[i]
  23. #define printv(v)      \
  24.     for (auto i : (v)) \
  25.     cout << i << " "
  26. #define fr0(i, n) for (ull(i) = 0; (i) < (n); (i)++)
  27. #define fr1(i, n) for (ull(i) = 1; (i) < (n); (i)++)
  28. #define fr(i, x, n) for (ull(i) = (x); (i) < (n); (i)++)
  29. #define _CRT_SECURE_NO_WARNING
  30. const ll MOD = 1000000007;
  31.  
  32. void Bustany() {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36. #ifndef ONLINE_JUDGE
  37.     freopen("./in.txt", "r", stdin), freopen("./out.txt", "w", stdout);
  38. #endif
  39. }
  40.  
  41. const ll N = 100;
  42. ll n, k;
  43. vector<sll> adj;
  44. vector<sll> dfsRoads;
  45. vector<sll> dfsRails;
  46. vector<sll> adj2;
  47. map<ll,ll> ans;
  48. sll s;
  49. //_2vll adj(N,vll);
  50. vb vis;
  51. vb viss;
  52.  
  53.  
  54. void dfs(ll i) {
  55.     vis[i] = 1;
  56.     s.insert(i);
  57.     for (auto j: adj[i]) {
  58.         if (!vis[j]) {
  59.             dfs(j);
  60.         }
  61.     }
  62. }
  63.  
  64. void dfss(ll i) {
  65.     vis[i] = 1;
  66.     s.insert(i);
  67.     for (auto j: adj2[i]) {
  68.         if (!vis[j]) {
  69.             dfss(j);
  70.         }
  71.     }
  72. }
  73.  
  74. void assign(ll i) {
  75.     viss[i] = 1;
  76.     dfsRoads[i]=s;
  77.     for (auto j: adj[i]) {
  78.         if (!viss[j]) {
  79.             assign(j);
  80.         }
  81.     }
  82. }
  83.  
  84. void assignR(ll i) {
  85.     viss[i] = 1;
  86.     dfsRails[i]=s;
  87.     for (auto j: adj2[i]) {
  88.         if (!viss[j]) {
  89.             assignR(j);
  90.         }
  91.     }
  92. }
  93.  
  94.  
  95. void solve() {
  96.     ll l;
  97.     cin >> n >> k >> l;
  98.     adj.assign(n + 1, {});
  99.     dfsRoads.assign(n + 1, {});
  100.     dfsRails.assign(n + 1, {});
  101.     vis.assign(n + 1, 0);
  102.     adj2.assign(n + 1, {});
  103.     viss.assign(n + 1, 0);
  104.     while (k--) {
  105.         ll u, v;
  106.         cin >> u >> v;
  107.         adj[u].insert(v);
  108.         adj[v].insert(u);
  109.     }
  110.     fr1(i, n+1) {
  111.         s.clear();
  112.         if (!vis[i]) {
  113.             viss.assign(n + 1, 0);
  114.             dfs(i);
  115.             assign(i);
  116.         }
  117.     }
  118.     while (l--) {
  119.         ll u, v;
  120.         cin >> u >> v;
  121.         adj2[u].insert(v);
  122.         adj2[v].insert(u);
  123.     }
  124.     vis.assign(n+1,0);
  125.     fr1(i, n+1) {
  126.         s.clear();
  127.         if (!vis[i]) {
  128.             viss.assign(n + 1, 0);
  129.             dfss(i);
  130.             assignR(i);
  131.         }
  132.     }
  133.     fr1(i,n+1){
  134.         for(auto j:dfsRoads[i]){
  135.             if(dfsRails[i].find(j)!=dfsRails[i].end())ans[i]++;
  136.         }
  137.     }
  138.     fr1(i,n+1)cout << ans[i]<<" ";
  139. }
  140.  
  141. int main() {
  142.     Bustany();
  143.     ll t = 1;
  144. //     cin >> t;
  145.     while (t--) {
  146.         solve();
  147.     }
  148. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iI30CQ
language:
C++ (gcc 8.3)
created:
4 hours 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!