PHÂN CHIA ĐỘI BÓNG

 PHÂN CHIA ĐỘI BÓNG

//Duyet Graph queue

#include<stdio.h>
#define N 500
typedef struct{
	int n;
	int A[N][N];
}Graph;
// Khoi tao do thi vo huong khong khuyen
void init_graph(Graph *G, int n){
	G->n=n;
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			G->A[i][j]=0;
}
void add_graph(Graph *G, int x, int y){
	G->A[x][y]=1;
	G->A[y][x]=1;
}
int adjacent(Graph *G, int x, int y){
	return G->A[x][y]!=0;
}
int degree(Graph *G, int x){
	int deg = 0,i;
	for(i=1;i<=G->n;i++)
		if(G->A[x][i]!=0)
			deg++;
	return deg;
}
typedef int ElementType;
typedef struct{
	ElementType data[500];
	int size;
}List;
//Khoi tao danh sach list
void make_list_null(List *L){
	L->size=0;
}
void push_list(List *L, int x){
	L->data[L->size]=x;
	L->size++;
}
ElementType element_at_list(List* L, int i) {
    return L->data[i-1];
}
int count_list(List* L) {
    return L->size;
}
int empty_list(List *L)
{
    return L->size == 0;
}

List neighbors(Graph *G, int x){
	List L;
	make_list_null(&L);
	int i;
	for(i=1;i<=G->n;i++){
		if(adjacent(G,x,i))
			push_list(&L,i);
	}
	return L;
}
void init_mark(Graph *G,int mark[]){
	int i;
	for(i=0;i<=G->n;i++){
		mark[i]=0;
	}
}
int color[100];
int fail; 
void colorize(Graph *G, int x, int c){
	if(color[x]==-1){
		color[x]=c;
		List L = neighbors(G,x);
		int i;
		for(i=0;i<L.size;i++){
				colorize(G,L.data[i],!c);
			}
	}
	else{
	if(color[x]!=c)
			fail=1;
}
}
int is_bigraph(Graph *G){
	int i;
	for(i=1;i<=G->n;i++)
		color[i]=-1;
	fail = 0;
	for(i=1;i<=G->n;i++)
	if(color[i]==-1)
		colorize(G,i,0);
	return !fail;
}

void DOIBONG(Graph *G , int x){
	if(!is_bigraph(G)){
		printf("IMPOSSIBLE");
	}
	else{
	int i;
	for(i=1;i<=G->n;i++){
			if(color[i]==0)
			printf("%d ",i);
	}	
		printf("\n");
		for(i=1;i<=G->n;i++){
			if(color[i]==1)
			printf("%d ",i);
	}
}
}		

int main(){
	Graph G;
	int n,i,m,j;
	int u,v;
	freopen("dt.txt","r",stdin);
	scanf("%d%d",&n,&m);
	init_graph(&G,n);
	for(i=0;i<m;i++){
			scanf("%d%d",&u,&v);
			add_graph(&G,u,v);
		}
	DOIBONG(&G,1);
	return 0;
}