fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <stdlib.h>
  5. #include <malloc.h>
  6. #define MAX 100
  7. typedef struct graph
  8.     {
  9.   int v;
  10.   struct graph *e;  
  11. }graph;
  12. int visited[101];
  13. int bfs[101];
  14. int main() {
  15.     int N,M,ui,vi,i,l,c,chld[101]={0},vrtx;
  16.     graph *g[MAX],*next;
  17.     scanf("%d%d",&N,&M);
  18.     i=1;
  19.     while(i<=N)
  20.         {
  21.         g[i]=(graph *)malloc(sizeof(graph));
  22.         g[i]->v=i;
  23.         g[i]->e=NULL;
  24.         i++;
  25.     }
  26.     i=0;
  27.     while(i<M)
  28.         {
  29.         scanf("%d%d",&ui,&vi);
  30.         next=g[ui];
  31.         while(next->e!=NULL)
  32.             next=next->e;
  33.         next->e = (graph *)malloc(sizeof(graph));
  34.             next->e->v=vi;
  35.             next->e->e=NULL;
  36.         next=g[vi];
  37.         while(next->e!=NULL)
  38.             next=next->e;
  39.         next->e = (graph *)malloc(sizeof(graph));
  40.             next->e->v=ui;
  41.             next->e->e=NULL;        
  42.         i++;
  43.     }
  44.     i=0;
  45.     l=1;
  46.     bfs[0]=1;
  47.     visited[0]=1;
  48.     while(i<N)
  49.         {
  50.             next = g[bfs[i]];
  51.             visited[next->v] = 1;
  52.             chld[next->v] = 1;
  53.                 next=next->e;        
  54.             while(next!=NULL)
  55.                 {
  56.                 if(visited[next->v] == 0)
  57.                 {
  58.                    bfs[l++]=next->v;
  59.                    chld[next->v] =1;
  60.                 }
  61.                 next=next->e;                
  62.             }
  63.         i++;
  64.     }
  65.     i=N-1;
  66.     while(i>=0)
  67.         {
  68.             next = g[bfs[i]];
  69.             visited[next->v] = 0;
  70.             vrtx = next->v;
  71.             next=next->e; 
  72.         l=0;
  73.             while(next!=NULL)
  74.                 {
  75.                 if(visited[next->v] == 1)
  76.                 {
  77.                    chld[next->v] += chld[vrtx];                
  78.                    l += 1;
  79.                 }
  80.                 next=next->e;                
  81.             }
  82.         if(l==0)
  83.             chld[vrtx] -= 1;
  84.         i--;
  85.     }
  86.     c=0;
  87.     for(i=1;i<=N;i++)
  88.         {
  89.         if(chld[i] % 2 == 0)
  90.             c+=1;  
  91.     }
  92.     printf("%d\n",c);
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 2188KB
comments (?)
stdin
copy 
10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8
stdout
copy 
2
https://ideone.com/VT1cZM
Even Tree
language:
C (gcc 8.3)
created:
9 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!