fork download
copy 
  1. //Varun
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define si(x) scanf("%d",&x)
  5. #define sll(x) scanf("%I64d",&x)
  6. #define pb push_back
  7. #define gcd(a,b) __gcd(a,b)
  8. #define F first
  9. #define S second
  10. #define SETBITS(x) __builtin_popcount(x)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define REP(a,b) for(int i=a;i<b;i++)
  13. #define REP2(a,b,c) for(int i=a;i<b;i+=c)   
  14. #define fastscan ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  15. #define debug(x) cerr<<#x<<" is "<<x<<endl
  16. #define INF INT_MAX
  17. #define N_INF INT_MIN
  18. typedef long long ll;
  19. typedef vector<int> vi;
  20. typedef vector<ll> vll;
  21. typedef pair<int,int> pi;
  22. typedef pair<ll,ll> pll;
  23.  
  24. #define TRACE
  25.  
  26. #ifdef TRACE
  27. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  28. template <typename Arg1>
  29. void __f(const char* name, Arg1&& arg1){
  30.   cerr << name << " : " << arg1 << std::endl;
  31. }
  32. template <typename Arg1, typename... Args>
  33. void __f(const char* names, Arg1&& arg1, Args&&... args){
  34.   const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  35. }
  36. #else
  37. #define trace(...)
  38. #endif
  39.  
  40. const ll mod = 1e9+7;
  41. const ll maxn = 2e5+5;
  42.  
  43. std::vector<ll>g[maxn];
  44.  
  45. ll dfs_par[maxn];//for cycle detection
  46. ll cyc_par[maxn];//to store root of each cycle
  47. ll vis[maxn];//1st dfs
  48. pll in[maxn], out[maxn];
  49. ll dfn[maxn];
  50. ll num = 0;
  51.  
  52. pll merge(pll a, pll b, ll x, ll y){
  53.     // if(x == 8){
  54.     //  cout << y << b.F << b.S << "\n";
  55.     // }
  56.     if(cyc_par[x] == cyc_par[y]){
  57.         return {a.F, a.S+b.F};
  58.     }
  59.     else{
  60.         return {a.F+b.F, a.S+b.S};
  61.     }
  62. }
  63.  
  64. pll unmerge(pll a, pll b, ll x, ll y){
  65.     if(cyc_par[x] == cyc_par[y]){
  66.         a.S -= b.F;
  67.     }
  68.     else{
  69.         a.F -= b.F, a.S -= b.S;
  70.     }
  71.     return a;
  72. }
  73.  
  74. void dfs(ll start, ll pre){
  75.     //trace(start, pre);
  76.     if(vis[start] == 0){
  77.         dfn[start] = num++;
  78.     }
  79.     vis[start]++;
  80.     for(ll i = 0; i < g[start].size(); ++i){
  81.         ll child = g[start][i];
  82.         if(child == pre)continue;
  83.  
  84.         if(vis[child] >= 2)continue;
  85.  
  86.         else if(vis[child] == 0){
  87.             dfs_par[child] = start;
  88.                 dfs(child, start);
  89.         }
  90.  
  91.         else{
  92.             ll dum=start;
  93.             while(cyc_par[dum] != child){
  94.                 cyc_par[dum] = child;
  95.                 dum = dfs_par[dum];
  96.             }
  97.         }
  98.     }
  99.     vis[start]++;
  100. }
  101.  
  102. void dfs_in(ll start, ll pre){
  103.     //trace(start, pre);
  104.     vis[start]++;
  105.     in[start] = {1, 0};
  106.  
  107.     ll back = -1;
  108.     for(auto child : g[start]){
  109.         if(child == pre)continue;
  110.         if(vis[child] == 0){
  111.             dfs_in(child, start);
  112.             in[start] = merge(in[start], in[child], start, child);
  113.         }
  114.         else if(vis[child] == 1){
  115.             back = child;
  116.         }
  117.     }
  118.     if(back != -1){
  119.         in[back] = merge(in[back], in[start], back, start);
  120.     }
  121.     vis[start]++;
  122. }
  123.  
  124. void dfs_out(ll start, ll pre){
  125.     vis[start]++;
  126.  
  127.     out[start] = {1, 0};
  128.  
  129.  
  130.     if(pre != 0){
  131.         out[start] = merge(out[start], out[pre], start, pre);
  132.         for(auto sibling : g[pre]){
  133.             ll count = 0;
  134.  
  135.             if(sibling == start)continue;// or sibling == dfs_par[pre])continue;
  136.  
  137.             if(cyc_par[start] == cyc_par[pre])++count;
  138.             if(cyc_par[pre] == cyc_par[sibling])++count;
  139.  
  140.             if(count == 2)continue;
  141.  
  142.             if(dfs_par[sibling] == pre){
  143.                 if(count){
  144.                     out[start] = merge(out[start], {0, in[sibling].F}, start, 0);
  145.                 }
  146.                 else
  147.                     out[start] = merge(out[start], in[sibling], start, sibling);
  148.             }
  149.         }
  150.     }
  151.  
  152.     for(auto child : g[start]){
  153.         if(child == pre)continue;
  154.         if(dfn[child] < dfn[start]){
  155.             out[start] = merge(out[start], out[child], start, child);
  156.             break;
  157.         }
  158.     }
  159.  
  160.     for(auto child : g[start]){
  161.         if(child == pre)continue;
  162.         if(vis[child] == 0){
  163.             dfs_out(child, start);
  164.         }
  165.     }
  166.     vis[start]++;
  167. }
  168.  
  169. ll ans(ll a, ll b){
  170.     if(dfs_par[a] == b){
  171.         swap(a, b);
  172.     }
  173.  
  174.     pll x = in[b];
  175.     pll y = {0, 0};
  176.  
  177.     for(auto sibling : g[a]){
  178.             ll count = 0;
  179.  
  180.             if(sibling == b or sibling == dfs_par[a])continue;
  181.  
  182.             //if(dfs_par[sibling] == a){
  183.             if(dfn[sibling] > dfn[a] and dfn[sibling] != dfn[b]){
  184.                        if(cyc_par[b] == cyc_par[a])count++;
  185.                        if(cyc_par[a] == cyc_par[sibling])++count;
  186.                        if(count == 2)continue;
  187.  
  188.                        if(count == 1)
  189.                          y = merge(y, {0, in[sibling].F}, a, 0);
  190.  
  191.                        else
  192.                           y = merge(y, in[sibling], a, sibling);
  193.                     }
  194.     }
  195.  
  196.     //pll x = in[b];
  197.     //pll y = unmerge(in[a], in[b], a, b);
  198.     //y = unmerge(y, {1, 0}, a, 0);
  199.     y = merge(y, out[a], a, b);
  200.     // if(b == 8)
  201.         //  trace(y.F, y.S);
  202.     // if(cyc_par[a] == cyc_par[b]){
  203.     //  return 1LL*x.F*y.F;
  204.     // }
  205.     // else{
  206.         return x.F*y.F + x.S*y.F + x.F*y.S;
  207.     //}
  208. }
  209.  
  210. std::vector<pll> edges;
  211.  
  212. int main()
  213. {
  214.     #ifndef ONLINE_JUDGE
  215.         freopen("input.txt", "r", stdin);
  216.         freopen("output.txt", "w", stdout);
  217.     #endif
  218.  
  219.     fastscan;
  220.  
  221.  
  222.     ll t;
  223.     cin >> t;
  224.     while(t--){
  225.         ll n, m;
  226.         num = 0;
  227.         cin >> n >> m;
  228.         edges.clear();
  229.         for(ll i = 0; i <= n; ++i){
  230.             g[i].clear();
  231.             dfs_par[i] = 0;
  232.             cyc_par[i] = i;
  233.             vis[i] = 0;
  234.         }
  235.  
  236.  
  237.  
  238.         for(ll i = 0; i < m; ++i){
  239.             ll u, v;
  240.             cin >> u >> v;
  241.             g[u].pb(v);
  242.             g[v].pb(u);
  243.             edges.pb({u, v});
  244.         }
  245.         vis[0] = 1;
  246.         for(ll i = 1; i <= n; ++i){
  247.             if(!vis[i]){
  248.                 dfs(i, 0);
  249.                 dfs_par[i] = 0;
  250.                  // for(int j = 1; j <= n; ++j){
  251.                  //     cout << cyc_par[j] <<'\n';
  252.                  // }
  253.                  // cout << '\n';
  254.                     for(int i = 0; i <= n; ++i)vis[i] = 0;
  255.                     vis[0] = 1;
  256.                 dfs_in(i, 0);
  257.                  // for(int j = 1; j <= n; ++j){
  258.                  //     cout << in[j].F << " " << in[j].S <<'\n';
  259.                  // }
  260.                  // cout <<"\n\n\n\n";
  261.                     for(int i = 0; i <= n; ++i)vis[i] = 0;
  262.                     vis[0] = 1;
  263.                 dfs_out(i, 0);
  264.                  // for(int j = 1; j <= n; ++j){
  265.                  //     cout << out[j].F << " " << out[j].S <<'\n';
  266.                  // }
  267.             }           
  268.         }
  269.  
  270.         //trace(out[8].F, out[8].S);                
  271.  
  272.         // for(int i = 1; i <= n; ++i){
  273.         //       cout << dfn[i] << " ";
  274.         // }
  275.         //cout << "\n";
  276.  
  277.         for(ll i = 0; i < edges.size(); ++i){
  278.             cout << ans(edges[i].F, edges[i].S) << "\n";
  279.         }
  280.     }
  281.     return 0;
  282. }
  283.  
  284. /* 
  285. Input
  286. 1
  287. 14 14
  288. 1 2
  289. 2 3
  290. 3 4
  291. 4 1
  292. 4 5
  293. 5 6
  294. 6 7
  295. 7 5
  296. 6 8
  297. 6 9
  298. 8 10
  299. 10 11
  300. 11 12
  301. 12 13
  302. 13 14
  303. */
  304.  
  305. /*
  306. Expected Output
  307. 1
  308. 1
  309. 2
  310. 2
  311. 11
  312. 14
  313. 7
  314. 2
  315. 25
  316. 9
  317. 24
  318. 21
  319. 16
  320. 9
  321. */
Success #stdin #stdout 0s 7764KB
comments ()
stdin
copy 
1
14 14
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 5
6 8
6 9
8 10
10 11
11 12
12 13
13 14
stdout
copy 
1
1
2
2
11
14
7
1
25
9
24
21
16
9
https://ideone.com/8OFIAS
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!