fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstdlib>
  6. #include<queue>
  7. #include<map>
  8. #include<set>
  9. #include<string>
  10. #include<vector>
  11. #include<cstring>
  12. #include<stack>
  13. #include<climits>
  14.  
  15. using namespace std;
  16.  
  17. int enemy[101][3];
  18. int A[101];
  19. int num[101];
  20. int flag[101];
  21. int visited[101];
  22.  
  23. bool dfs(int node,int start,int count){
  24.     int i;
  25.     if(node == start && visited[node] == 1)
  26.         return true;
  27.     visited[node]++;
  28.     for(i=1;i<=num[node];i++){
  29.         if(!visited[enemy[node][i]] || (enemy[node][i] == start && count >= 2))
  30.             return dfs(enemy[node][i],start,count+1);
  31.     }
  32.     return false;
  33. }
  34.  
  35. int cycle(int node,int start,int count){
  36.     int i;
  37.     flag[node] = 1;
  38.     if(node == start && visited[node] == 1)
  39.         return count;
  40.     visited[node]++;
  41.     for(i=1;i<=num[node];i++){
  42.         if(!visited[enemy[node][i]] || (enemy[node][i] == start && count >= 2))
  43.             return cycle(enemy[node][i],start,count+1);
  44.     }
  45. }
  46.  
  47. int main(){
  48.     int m,n,i,j,a,b,k,temp,t1,t2,count;
  49.     scanf("%d%d",&n,&m);
  50.     for(i=1;i<=m;i++){
  51.         scanf("%d%d",&a,&b);
  52.         num[a]++;
  53.         num[b]++;
  54.         enemy[a][num[a]] = b;
  55.         enemy[b][num[b]] = a;
  56.     }
  57.     t1 = 0;
  58.     t2 = 0;
  59.     temp = n;
  60.     for(i=1;i<=n;i++){
  61.         if(!flag[i] && num[i] == 2){
  62.             if(dfs(i,i,0)){
  63.                 for(j=1;j<=n;j++) visited[j] = 0;
  64.                 count = cycle(i,i,0);
  65.                 n-=count;
  66.                 t1+=count/2;
  67.                 t2+=count/2;
  68.             }
  69.         }
  70.     }
  71.     t1+=n/2;
  72.     t2+=n/2;
  73.     printf("%d\n",temp-t1-t2);
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.02s 2684KB
comments (?)
stdin
copy 
4 3
1 3
3 2
2 4
stdout
copy 
0
https://ideone.com/giuYZ
language:
C++ (gcc 8.3)
created:
12 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!