DFS using adjacency lists much slower than using a C++ vector?

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Trying to solve 862B about the maximum number of edges one can add to a certain tree so that it's still a bipartite graph. I went with the "let's code everything ourselves" approach and limited myself to C. Here's my code.

Code

    #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);
    }

I looked at others' submissions and they used similar approaches but almost all of them used the vector class in C++. My code works fine on most tests including ones with n = 100k, running them in <50 ms, but then there's a test where one node has loads of edges and it times out at >2000 ms. Why? Even if you use a vector, the amount of recursive calls should still be the same, which should be the limiting factor here in terms of speed, right? Do I have an infinite loop?

Комментарии (3)

Написать комментарий?

Siriuslight

7 лет назад, # |

+16

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.

→ Ответить

Hyeokshin

7 лет назад, # ^ |

Thanks!

knightL

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.

Блог пользователя Hyeokshin