问题是:已经给出了一个由N节点和M边组成的无向图。该图可以由自循环以及多条边组成。此外,您还收到了Q查询。对于每个查询,您将获得2个整数A和B。您只需要找到节点A和节点B之间是否存在边。如果是,则打印"是"(不带引号(;否则,打印"否"(不加引号(。
我的代码:
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector< vector<int> > v;
int a,b;
vector<int>temp;
while(m--)
{
cin>>a>>b;
temp.push_back(a);
v.push_back(temp);
v[a].push_back(b);
temp.clear();
}
int q;
cin>>q;
while(q--)
{
cin>>a>>b;
int flag=0;
for(int i=0;i<v[a].size();i++)
{
if(v[a][i]==b)
{
cout<<"YES"<<endl;
flag=1;
break;
}
}
if(flag!=1)
cout<<"NO"<<endl;
}
return 0;
}
我得到分割错误。我做错了什么?
例如,当您想添加边(3,5)
时,将3推入空向量(temp
(,然后将push_back
temp推入v
。所以现在v
的大小是1。然后尝试push_back
5到v[3]
:
v[a].push_back(b);
v[3]
不存在,因为您的v
只有1个项目。因此,分割错误。
我该怎么办
因为您事先知道节点数(n
(,所以可以用节点数初始化v
(如果要使用1-索引,则为n+1
(。因此v
将有n
空vector
s。然后您可以安全地将push_back
项放入v[a]
中。此外,因为图对于每条边都是无向的(a,b(,所以应该同时执行v[a].push_back(b)
和v[b].push_back(a)
。
下面是一个工作示例:
int n,m;
cin>>n>>m;
vector< vector<int> > v(n+1); // initialize v with (n+1) empty vectors
// because we want to use 1-indexing
int a,b;
while(m--)
{
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}