N-те населени места на един район, номерирани от 1 до N, са свързани с пътища. След като
паднал сняг, останали проходими само M пътни отсечки, всяка от които свързва две от населените
места. Изнервени граждани, които пътуват от едно населено място до друго – по работа, или просто
така, атакуват многократно операторите на телефон 112 с въпроси от вида „Може ли да се стигне от
селището X до селището Y в момента?“
Напишете програма no112C, която да помага на операторите на телeфон 112 да отговарят
бързо на въпросите.
Вход
На първия ред на стандартния вход ще бъдат зададени числата N и M. На всеки от следващите
M реда – по два номера на град, свързани с проходима пътна отсечка. Следва ред с броя Q на
обажданията и Q реда с по два номера на град, на всеки от тях – населените места, за които се отнася
съответният въпрос.
Изход
На стандартния изход програмата трябва да изведе отговорите на зададените въпроси – битов
низ (последователност от нули и единици) с дължина Q знака, като знакът 0 на i–та позиция
означава, че за въпроса с номер i не е възможно да се стигне от едното населено място до другото, а
знакът 1 – че може.
Ограничения
2 ≤ N ≤ 1000
1 ≤ M ≤ 2N
0 < Q ≤ 100000
Пример
Вход Изход
9 9 100
1 2
3 4
5 6
7 8
9 5
7 2
8 2
6 9
1 7
3
1 8
6 2
4 7
На конзолата ми върви, но като я пускам на система се преебава... Не знам работили ли сте на система, но тя е на Linux, а компютърът ми компилира под Windous и сигурно от там идва проблема. Дава ми Compilation Error като грешка. Или в двойния vector (vector <vector <int>> car; ) или в създаването на празни под вектори после (car.push_back(vector<int>()); ) и проблемът, според мен, но не мога да си обясня защо и как да го оправя. Ето кода, ако някой разбира, моля ви, да ми помогне:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector <char> K;
vector <vector <int>> car;
int key, used[1005];
void bfs (int from, int to)
{
queue <int> fak;
fak.push(from);
used[from]=1;
key=0;
while (!fak.empty())
{
int t=fak.front();
if (fak.front()==to)
{
K.push_back('1');
key=1;
break;
}
fak.pop();
for (int z=0; z<car[t].size(); z++)
{
if (used[car[t][z]]!=1) fak.push(car[t][z]);
used[car[t][z]]=1;
}
}
if(key!=1)
{
K.push_back('0');
}
}
int main ()
{
int N, M, f, t;
cin>>N>>M;
for (int i=0; i<=N; i++)
car.push_back(vector<int>());
for (int y=0; y<M; y++)
{
cin>>f>>t;
car[f].push_back(t);
car[t].push_back(f);
}
int Q, f1, t1;
cin>>Q;
for (int h=0; h<Q; h++)
{
cin>>f1>>t1;
for (int w=1; w<=N; w++) used[w]=0;
bfs (f1, t1);
}
for (int j=0; j<K.size(); j++) cout<<K[j];
cout<<endl;
return 0;
}