#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct adjNode {
int v;
struct adjNode *next;
}adjNode;
adjNode **Adj;
typedef struct vInfo {
int visited;
int parent;
int set;
}vInfo;
vInfo *Info;
int n;
int visited = 0;
long long setN[2] = { 1, 0 };
void dfs(int u);
void insertEdge(int v1, int v2);
void initInfo();
int main(void) {
scanf("%d", &n);
Adj = calloc((n + 1), sizeof(struct adjNode *));
Info = malloc((n + 1) * sizeof(struct vInfo));
initInfo();
int v1, v2;
for (size_t i = 1; i < n; i++)
{
scanf("%d %d", &v1, &v2);
insertEdge(v1, v2);
}
dfs(1);
finish();
}
void dfs(int u) {
Info[u].visited = 1;
visited++;
for (adjNode *vAdj = Adj[u]; vAdj != NULL; vAdj = vAdj->next)
{
if (!Info[vAdj->v].visited)
{
Info[vAdj->v].parent = u;
Info[vAdj->v].set = 1 - Info[u].set;
setN[Info[vAdj->v].set]++;
dfs(vAdj->v);
if (visited == n)
{
finish();
}
}
}
}
void insertEdge(int v1, int v2) {
adjNode *v1v2 = malloc(sizeof(struct adjNode));
v1v2->next = NULL;
v1v2->v = v2;
adjNode *v2v1 = malloc(sizeof(struct adjNode));
v2v1->next = NULL;
v2v1->v = v1;
adjNode *iter;
if (Adj[v1] == NULL)
Adj[v1] = v1v2;
else {
for (iter = Adj[v1]; iter->next != NULL; iter = iter->next);
iter->next = v1v2;
}
if (Adj[v2] == NULL)
Adj[v2] = v2v1;
else {
for (iter = Adj[v2]; iter->next != NULL; iter = iter->next);
iter->next = v2v1;
}
}
void initInfo() {
for (size_t i = 1; i <= n; i++)
{
Info[i].visited = 0;
Info[i].parent = -1;
Info[i].set = 0;
}
}
void finish() {
printf("%lld", setN[0] * setN[1] - (n - 1));
exit(0);
}
List uses pointers to access adjacent elements. While vector uses indexing just like an array. Due to direct access vector is comparatively much faster as compared to list.
Thanks!
Your insertEdge takes too long finding list's tail. Each call takes O(size) time and if all edges are adjacent to same vertex you spend O(n^2) which is too much. You should either store tail or push front.