-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathEven tree
204 lines (171 loc) · 4.88 KB
/
Even tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int ans=0;
struct QNode
{
int key;
struct QNode *next;
};
// The queue, front stores the front node of LL and rear stores ths
// last node of LL
struct Queue
{
struct QNode *front, *rear;
};
// A utility function to create a new linked list node.
struct QNode* newNode(int k)
{
struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
temp->key = k;
temp->next = NULL;
return temp;
}
// A utility function to create an empty queue
struct Queue *createQueue()
{
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
// The function to add a key k to q
void enQueue(struct Queue *q, int k)
{
// Create a new LL node
struct QNode *temp = newNode(k);
// If queue is empty, then new node is front and rear both
if (q->rear == NULL)
{
q->front = q->rear = temp;
return;
}
// Add the new node at the end of queue and change rear
q->rear->next = temp;
q->rear = temp;
}
// Function to remove a key from given queue q
struct QNode *deQueue(struct Queue *q)
{
// If queue is empty, return NULL.
if (q->front == NULL)
return NULL;
// Store previous front and move front one node ahead
struct QNode *temp = q->front;
q->front = q->front->next;
// If front becomes NULL, then change rear also as NULL
if (q->front == NULL)
q->rear = NULL;
return temp;
}
// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
// A structure to represent an adjacency list
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void DFS(struct Graph* graph)
{
int i,time;
bool visited[graph->V];
for(i=0;i<graph->V;i++)
visited[i]=false;
int initial[graph->V];
for(i=0;i<graph->V;i++)
initial[i]=-1;
int final[graph->V];
for(i=0;i<graph->V;i++)
final[i]=-1;
int parent[graph->V];
for(i=0;i<graph->V;i++)
parent[i]=-1;
time=0;
for(i=0;i<graph->V;i++)
if(!visited[i])
DFS_Visit(graph,i,visited,initial,final,parent,time);
}
int DFS_Visit(struct Graph* graph,int u,bool visited[],int initial[],int final[],int parent[],int time)
{
struct AdjListNode* pCrawl;
visited[u]=true;
int num_vertex=0;
time =time+1;
initial[u]=time;
for(pCrawl = graph->array[u].head;pCrawl!=NULL;pCrawl = pCrawl->next){
//printf("\n");
if(!visited[(pCrawl->dest)]) {
parent[pCrawl->dest]=u;
int c= DFS_Visit(graph,pCrawl->dest,visited,initial,final,parent,time);
printf("%d",c);
if(c%2==0)
ans++;
else
num_vertex+=c;
}
}
time=time+1;
final[u]=time;
return num_vertex+1;
}
int main()
{
int V,E,m,n;
scanf("%d %d",&V,&E);
struct Graph* graph = createGraph(V);
for(int i=0;i<E;i++)
{
scanf("%d %d",&m,&n);
//printf("%d %d",m,n);
addEdge(graph,m-1,n-1);
}
DFS(graph);
// printf("%d",x);
printf("%d",ans);
return 0;
}