fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cstring>
  5.  
  6. #define MAXN 10001
  7.  
  8. using namespace std;
  9.  
  10. int N, M;
  11. vector<int> G[MAXN];
  12.  
  13. int Time = 0; // neznaeh che "time" e klucova duma . . .
  14. int disc[MAXN], parent[MAXN], low[MAXN], has[MAXN];
  15. bool visited[MAXN];
  16.  
  17. void read()
  18. {
  19.     memset(low,0,sizeof(low));
  20.     memset(disc,0,sizeof(disc));
  21.     memset(parent,0,sizeof(parent));
  22.     memset(has,0,sizeof(has));
  23.     memset(visited,0,sizeof(visited));
  24.  
  25.     Time = 0;
  26.  
  27.     scanf("%d %d", &N, &M);
  28.  
  29.     for(int i=1;i<=N;i++) {
  30.         G[i].clear();
  31.     }
  32.  
  33.     for(int i = 0; i < M; i++)
  34.     {
  35.         int u, v;
  36.         scanf("%d %d", &u, &v);
  37.         u++;
  38.         v++;
  39.  
  40.         G[u].push_back(v);
  41.         G[v].push_back(u);
  42.     }
  43. }
  44.  
  45. void DFS_Trajan(int u)
  46. {
  47.     visited[u] = true;
  48.  
  49.     ++Time;
  50.     disc[u] = Time;
  51.     low[u] = Time;
  52.  
  53.     int sz = G[u].size();
  54.  
  55.     for(int i = 0; i < sz; i++)
  56.     {
  57.         int v = G[u][i];
  58.  
  59.         if(!visited[v])
  60.         {
  61.             parent[v] = u;
  62.             DFS_Trajan(v);
  63.         }
  64.  
  65.         if(v != parent[u])
  66.             low[u] = min(low[u], low[v]);
  67.             //low[u] = min(low[u], disc[v]);
  68.     }
  69. }
  70.  
  71. void solve()
  72. {
  73.     DFS_Trajan(1);
  74.  
  75.     int cnt = 0;
  76.  
  77.     for(int u = 1; u <= N; u++)
  78.     {
  79.         int sz = G[u].size();
  80.  
  81.         for(int i = 0; i < sz; i++)
  82.         {
  83.             int v = G[u][i];
  84.  
  85.             //printf("{%d %d}, {%d %d}\n", v, low[v], u, low[u]);
  86.  
  87.             if(low[v] != low[u])     // ako sa v razlichni componenti
  88.             {
  89.                 //printf("{%d %d}, {%d %d}\n", v, low[v], u, low[u]);
  90.  
  91.                 if(has[low[u]] != 0)  // nqma smisyl da uvelichavame "cnt"
  92.                 {
  93.                     if(has[low[u]] == 1)
  94.                     {
  95.                         has[low[u]] = 2;
  96.                         cnt--;
  97.                     }
  98.                     continue;        // zashtoto shte namerim drugo rebro ot "v" -> "w" , kydeto "w"
  99.                 }                    // ni e naslednik na v
  100.  
  101.                 has[low[u]] = 1;
  102.                 cnt++;
  103.             }
  104.         }
  105.     }
  106.  
  107.     //printf("%d\n", cnt);
  108.  
  109.     int ans = cnt / 2;
  110.     ans += (cnt % 2);       // Shtot se opravq pri kontra primera . . .
  111.  
  112.     printf("%d\n", ans);
  113. }
  114.  
  115. int main()
  116. {
  117.     int i,t;
  118.  
  119.     scanf("%d", &t);
  120.  
  121.     for(i=1;i<=t;i++) {
  122.         read();
  123.         printf("Case %d: ", i);
  124.         solve();
  125.     }
  126.  
  127.     return 0;
  128. }
Success #stdin #stdout 0s 3008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/g0FOXc
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!