京东笔试 完全多部图

#include <stdio.h>
#include <stdlib.h>

int Insert(int *G, int *U, int Va, int Vb, int N);

int main(int argc, char const *argv[])
{
int *U;
int *G;
int T,N,M,X,Y;

scanf("%d", &T);
while(T>0)                      //测试T组数据
{
scanf("%d %d", &N, &M);
U = (int *)malloc(sizeof(int)*N);

for(int i = 0; i<N; i++)    //初始化并查集
{
U[i]=-1;
}

G = (int *)malloc(sizeof(int)*N*N);

for(int i = 0; i<N; i++)  //初始化图
{
for(int j = 0;j<N; j++)
{
G[i*N + j] = 0;
}
}

while(M > 0)              // 输入M条边
{
scanf("%d %d", &X, &Y);
G[(X-1)*N+(Y-1)] = 1;  //存在边的两点图中标记
G[(Y-1)*N+(X-1)] = 1;
M--;
}

for(int i = 0; i<N; i++)  //遍历图
{
for(int j = 0; j<N; j++)
{
if(i == j)
continue;
if(G[i*N + j]!=1) //无边的点尝试合并
{
if(Insert(G, U, i, j, N)==0) //测试是否能合并
{
printf("No\n");
goto Next;
}
}
}
}
printf("Yes\n");
}

return 0;
}

int Insert(int *G, int *U, int Va, int Vb, int N)
{
if(U[Va]==-1)               //Va是单独的集合
{
if(U[Vb] == -1)         //Vb是单独的集合
{
U[Vb] = Va;            //将Vb加入Va的集合
return 1;
}
else                    //Vb不是单独的集合
{
int Tmp = Vb;
while(U[Tmp] != -1)    //测试Va和每一个Vb集合中的点是否有边
{
if(G[ Va*N+U[Tmp] ] == 1) //有边存在，不是完全图
return 0;
else
Tmp = U[Tmp];
}
U[Va] = Vb;
return 1;          //将Va加入Vb的集合
}
}
else                        //Va不是单独的集合
{
if(U[Vb] == -1)            //Vb是单独的集合
{
int Tmp = Va;
while(U[Tmp] != -1)//测试Vb和每一个Va集合中的点是否有边
{
if(G[ Vb*N+U[Tmp] ] == 1) //有边存在，不是完全图
return 0;
else
Tmp = U[Tmp];
}
U[Vb] = Va;
return 1;            //将Vb加入Va的集合
}
else                    //Vb不是单独的集合
{
int Tmp = Vb;        //测试Vb集合每一个点和每一个Va集合中的点是否有边
while(U[Tmp] != -1)
{
int Tmp2 = Va;
while(U[Tmp2] != -1)
{
if(G[ Tmp2*N+U[Tmp] ] == 1)//有边存在，不是完全图
return 0;
else
Tmp2 = U[Tmp2];
}
Tmp = U[Tmp];
}
U[Tmp] = Va;
return 1;        //将Vb加入Va的集合
}
}
}
#京东##笔试题目#