=1;
}
p=p->next;
}
}
return 0;
}
int main()
{
memset(vis,0,sizeof(vis));
create();
int a1,a2,a,b;
cin>>a>>b;
a1=bfs(a,b);
memset(vis,0,sizeof(vis));
a2=bfs(b,a);
if(a1==1){
cout<<1<
}else if(a2==1){
cout<<-1<
}else{
cout<<0<
}
}
小Q最近在玩一个嵌入式开发板，看着板子上的一堆电容，他想比较板子上电容数量的多少。第一行给定比较次数n，
接下来n行，每行给定两个板子的编号a1,a2,编号从1开始。每行第一个元素a1为第一次比较中板子上电容数量较多的
板子编号，第二个元素a2为板子上电容数量较少的板子编号。最后一行为要比较的两块板子的编号a,b.请返回这两块
板子上电容数量大小的关系，若a更多返回1，b更多返回-1，无法判断返回0。输入数据保证合法，不会有矛盾的情况出现。
思路：看作有向图，从a开始遍历，如果可以到b，则a更多，然后从b开始再遍历一次，如果可以到a,则b更多，否则输出0
#include
#include
#include
#include
using namespace std;
//邻接表
typedef struct ArcNode{
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef struct VNoode{
ArcNode *firstArc;
}VNode;
VNode G[100];
int vis[100];
//创建邻接表
void create(){
int n,a,b;
for(int i=0;i<100;i++){
G.firstArc=NULL;
}
cin>>n;
ArcNode *p;
for(int i=0;i
p=(ArcNode*)malloc(sizeof(ArcNode));
cin>>a>>b;
p->adjvex=b;//头插法
p->next=G[a].firstArc;
G[a].firstArc=p;
}
}
int bfs(int v,int d){
queue q;
q.push(v);
vis[v]=1;
while(!q.empty()){
ArcNode *p;
int s=q.front();
if(s==d) return 1;
q.pop();
p=G.firstArc;
while(p!=NULL){
int i=p->adjvex;
if(!vis){
q.push(i);
vis=1;
}
p=p->next;
}
}
return 0;
}
int main()
{
memset(vis,0,sizeof(vis));
create();
int a1,a2,a,b;
cin>>a>>b;
a1=bfs(a,b);
memset(vis,0,sizeof(vis));
a2=bfs(b,a);
if(a1==1){
cout<<1<
}else if(a2==1){
cout<<-1<
}else{
cout<<0<
}
}
举报
举报
