给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:
按照"{ v1v​2… v​k}"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxVertexNum 10  /* 最大顶点数设为10 */
typedef struct GNode *PtrToGNode;
struct GNode{
    
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    int G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
int Visited[MaxVertexNum]; /* 顶点的访问标记 */
/* 队列定义 */
struct QNode{
    
	int Data[MaxVertexNum];
	int front;
	int rear;
};
typedef struct QNode* Queue;
int Isempty(Queue Q)
{
    
	if(Q->front==Q->rear)
	return 1;
	return 0;
}
void enqueue(Queue Q,int P)
{
    
	Q->rear=(Q->rear+1)%MaxVertexNum;
	Q->Data[Q->rear]=P;
}
int outqueue(Queue Q)
{
    
	Q->front=(Q->front+1)%MaxVertexNum;
	return Q->Data[Q->front];
}
Queue CreatQ(void)
{
    
	Queue Q=(Queue)malloc(sizeof(struct QNode));
	Q->front=Q->rear=0;
	return Q;
}
MGraph Create(void)
{
    
	MGraph g=(MGraph)malloc(sizeof(struct GNode));
	g->Ne=g->Nv=0;
	int i,j;
	for(i=0;i<MaxVertexNum;i++)
	{
    
		Visited[i]=0;
		for(j=0;j<MaxVertexNum;j++)
		{
    
			g->G[i][j]=0;
		}
	}
	return g;
}
void Visit( int V )
{
    
    printf(" %d", V);
}
int alone[MaxVertexNum];
void Findalone(MGraph Graph)
{
    
	int k,m;
	for(k=0;k<Graph->Nv;k++)
	{
    
		for(m=0;m<Graph->Nv;m++)
		{
    
			if(Graph->G[k][m])
			{
    
				alone[k]=0;
				alone[m]=0;
				break;
			}
		}
		if(m==Graph->Nv)
		alone[k]=1;
	}
}
void Insert(MGraph Graph,int a,int b)
{
    
	Graph->G[a][b]=1;
	Graph->G[b][a]=1;
}
void reset(MGraph Graph)
{
    
	int i;
	for(i=0;i<Graph->Nv;i++)
	{
    
		Visited[i]=0;
	}
}
int Isask(int V)
{
    
	if(!Visited[V])return 0;
	return 1;
}
void DFS( MGraph Graph, int V, void (*Visit)(int) )
{
    
	if(!Visited[V])
	{
    
		Visit(V);
		Visited[V]=1;
		int i;
		for(i=0;i<Graph->Nv;i++)
		{
    
			if(Graph->G[V][i]&&!Visited[i])
			{
    
				DFS(Graph,i,Visit);
			}
		}
	}
}
void BFS( MGraph Graph, int V, void (*Visit)(int) )
{
    
	if(!Visited[V])
	{
    
		Queue Q=CreatQ();
		Visit(V);
		Visited[V]=1;
		int v,w;
		enqueue(Q,V);
		while(!Isempty(Q))
		{
    
			v=outqueue(Q);
			for(w=0;w<Graph->Nv;w++)
			{
    
				if(!Visited[w]&&Graph->G[v][w])
				{
    
					Visit(w);
					Visited[w]=1;
					enqueue(Q,w);
				}
			}
		}
	}
	
}
int main()
{
    
	int n,e;scanf("%d%d",&n,&e);
	int i,j,a,b;
	MGraph Graph=Create();
	Graph->Nv=n;
	Graph->Ne=e;
	for(i=0;i<e;i++)
	{
    
		scanf("%d%d",&a,&b);
		Insert(Graph,a,b);
	}
	Findalone(Graph);
	for(i=0;i<n;i++)
	{
    
		if(!Isask(i))
		{
    
			printf("{");
			DFS(Graph,i,Visit);
			printf(" }\n");
		}else if(alone[i]==1)
		{
    
			printf("{");
			printf(" %d",i);
			printf(" }\n");
		}
	}
	reset(Graph);
	for(i=0;i<n;i++)
	{
    
		if(!Isask(i))
		{
    
			printf("{");
			BFS(Graph,i,Visit);
			printf(" }\n");
		}else if(alone[i]==1)
		{
    
			printf("{");
			printf(" %d",i);
			printf(" }\n");
		}
	}
	return 0;
}