はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

ALDS1_11_D Connected Components

問題
グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge

連結生成分解の問題。GRL_3_Cの"強"連結生成分解の問題を解いたのですが、TLEとなってしまいました。
じゃあALDSの連結生成分解ならできるんじゃね?ってことで挑戦したら解けました。

#include<stdio.h>
#include<stdlib.h>
#define LARGE 100000


int V,E;
int color=0;

typedef struct list{
	int id;
	struct list *next;
}list;


list * makelist(int x){
	list *new=malloc(sizeof(list));
	new->id=x;
	new->next=NULL;
	return new;
}

void list_insert(list* L[],int x,list *new){
	list **p=&L[x];
	
	while((*p)!=NULL){
		p=&((*p)->next);
	}
	(*p)=new;
	
	return;
}

int push(int stack[],int x,int top){
	stack[top++]=x;
	return top;
}

int pop(int stack[],int *top){
	(*top)--;
	return stack[*top];
}

void dfs(int C[],int x,list* L[]){
	int stack[LARGE];
	int top=0;
	int temp;
	list *p;
	
	color++;
	top=push(stack,x,top);
	while(top>0){
		temp=pop(stack,&top);
		if(C[temp]==0)C[temp]=color;
		p=L[temp];
		while(p!=NULL){
			if(C[p->id]==0){
				top=push(stack,p->id,top);
				C[p->id]=color;
			}
			p=p->next;
		}
	}
	
	return;
}

int main(){
	int i,j;
	int s,t,q;
	int x,y;
	list *L[LARGE];
	list *new;
	int C[LARGE];
	
	scanf("%d %d",&V,&E);
	
	for(i=0;i<V;i++){
		L[i]=NULL;
		C[i]=0;
	}
	
	for(i=0;i<E;i++){
		scanf("%d %d",&s,&t);
		new=makelist(t);
		list_insert(L,s,new);
		new=makelist(s);
		list_insert(L,t,new);
	}
	
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d %d",&x,&y);
		if(C[x]==0)dfs(C,x,L);
		if(C[y]==0)dfs(C,y,L);
		if(C[x]==C[y])printf("yes\n");
		else printf("no\n");
	}
		
	
	return 0;
	
}

お手製スタック恥ずかしい。