#define EOL NULL
typedef int ListElementType;
typedef struct _My_ListNode{
	ListElementType element;
	struct _My_ListNode *next;
	struct _My_ListNode *prev;
} MyListNode, *Position;

typedef struct _List_Record{
	MyListNode firstDummy;
	MyListNode lastDummy;
	int size;
} *List;

List List_Create(void);
void List_Delete(List L);
bool List_IsEmpty(List L);
void List_InsertIntoFirst(List L, ListElementType X);
ListElementType List_DeleteLastElement(List L);
ListElementType List_Retrieve(Position P);
Position List_FirstPosition(List L);
Position List_PositionAdvance(List L, Position P);
/*以上是关于链表的声明*/
void BFS(List *G, int n, int source, bool *color);

int countComponents(int n, int **edges, int edgesSize, int *edgesColSize)
{
    if(n == 0) return 0;
    bool color[n];
    int i, ans = 0;
    List AdjL[n];
    for(i = 0; i < n; i++){
        color[i] = 0;
        AdjL[i] = List_Create();
    }
    for(i = 0; i < edgesSize; i++){
        List_InsertIntoFirst(AdjL[edges[i][0]], edges[i][1]);
        List_InsertIntoFirst(AdjL[edges[i][1]], edges[i][0]);
    }
    for(i = 0; i < n; i++){
        if(!color[i]){
            ans++;
            BFS(AdjL, n, i, color);
        }
    }
    for(i = 0; i < n; i++)
        List_Delete(AdjL[i]);
    return ans;
}

void BFS(List *G, int n, int source, bool *color)
{
    int u, v;
    List queue = List_Create();
    Position P;
    color[source] = 1;
    List_InsertIntoFirst(queue, source);
    while(!List_IsEmpty(queue)){
        u = List_DeleteLastElement(queue);
        P = List_FirstPosition(G[u]);
        while(P != EOL){
            v = List_Retrieve(P);
            P = List_PositionAdvance(G[u], P);
            if(!color[v]){
                color[v] = 1;
                List_InsertIntoFirst(queue, v);
            }
        }
    }
    List_Delete(queue);
    return;
}

/*List routines*/
List List_Create(void)
{
	List L = malloc(sizeof(struct _List_Record));
	L->size = 0;
	L->firstDummy.prev = NULL;
	L->firstDummy.next = &(L->lastDummy);
	L->lastDummy.next = NULL;
	L->lastDummy.prev = &(L->firstDummy);
	return L;
}

void List_Delete(List L)
{
	MyListNode *p = L->firstDummy.next, tmp;
	while(p != &(L->lastDummy)){
		p = p->next;
		free(p->prev);
	}
	free(L);
	return;
}

bool List_IsEmpty(List L)
{
	return L->size == 0;
}

void List_InsertIntoFirst(List L, ListElementType X)
{
	MyListNode *tmp = L->firstDummy.next;
	L->firstDummy.next = malloc(sizeof(MyListNode));
	L->firstDummy.next->prev = &(L->firstDummy);
	L->firstDummy.next->next = tmp;
	tmp->prev = L->firstDummy.next;
	L->firstDummy.next->element = X;
	L->size++;
	return;
}

ListElementType List_DeleteLastElement(List L)
{
	ListElementType ret = L->lastDummy.prev->element;
	L->lastDummy.prev = L->lastDummy.prev->prev;
	free(L->lastDummy.prev->next);
	L->lastDummy.prev->next = &(L->lastDummy);
	L->size--;
	return ret;
}

ListElementType List_Retrieve(Position P)
{
	return P->element;
}

Position List_PositionAdvance(List L, Position P)
{
	P = P->next;
	return (P != &(L->lastDummy)) ? P : EOL;
}

Position List_FirstPosition(List L)
{
	return (L->size != 0) ? L->firstDummy.next : EOL;
}