using namespace std;
const int max_n = 100005;
vector<int> g[max_n];
bool used[max_n];//navbatga qo’yilganligini belgilab qo’yadigan mantiqiy oz’garuvch
queue<int> q;//navbat
int d[max_n];
int main() {
int n, m; // Uchlar va bog’lanishlar soni
cin>>n>>m;
for (int i = 1; i <= m; i++) {
int v1, v2;
cin>>v1>>v2;
g[v1].push_back(v2); // Orientrlanmagan graf uchun
g[v2].push_back(v1);
}
q.push(1);// Boshlang'ich uchni navbatga qo'yish
used[1] = 1;
while (!q.empty()) { // Navbatdagi uch bo'sh bo'lmagunga qadar davom ettiramiz
int v = q.front(); // Navbatning boshidagi uchni olamiz
cout<endl;
q.pop(); // Navbatdan uni o'chirib tashlaymiz
for (int i = 0; i < (int)g[v].size(); i++) { // v uchning qo'shnilarini ko'rib chiqamiz
int to = g[v][i]; // v uchning navbatdagi qo'shnisi
if (!used[to]) { // agar u hali ko'rilmagan bo'lsa
used[to] = 1; // uni ko'rilgan uchlar qatoriga qo'shamiz
q.push(to); // uni navbat oxiriga qo'yamiz
d[to] = d[v]+1;
}
}
}
}
Algoritmning ishlashini misolda ko’rib chiqaylik:
Hozir qaralayotgan uch
Navbatga qo’yilgan uch
Navbatdan o’chirilgan uch
Hozir qaralayotgan qirra
Shuning bilan barcha uchlar va barcha bog’lanishlar bir martadan ko’rib chiqiladi. Natijada boshlang’ich uchga bo’g’langan barcha uchlar ko’rib chiqiladi.
Algoritm ishlash vaqti O(n+m). n – uchlar soni, m – bog’lanishlar soni.
Qo’llanilishi:
Grafning komponentalarni aniqlash. Buning uchun navbatdagi hali ko’rilmagan uch orqali kenglik bo’yicha izlashni boshlaymiz. Bu o’tib chiqishda u unga bog’langan barcha uch orqali o’tib chiqadi, va ular bitta graf komponentasi deb aytiladi. Komponentalar soni bfs funksiyasiga necha marta murojaat qilganimiz soni. used massivida true qiymatni qabul qilgan barcha uchlar kenglik bo’yicha izlashni boshlagan uch orqali borib bo’ladi.
Grafdagi eng qisqa yo’l topish. Grafda yo’l bu – bir uchdan boshqa uchga boradigan uchlar va qirralar ketma-ketligiga aytiladi. Qirralar soni esa yo’l uzunligi deb ataladi. Eng qisqa yo’l qirralar soni eng kichik bo’ladiga yo’lga aytiladi. Chuqurlik bo’yicha izlash algoritmi aynan qirralar soni bo’ticha eng qisqa yo’lni topadi. Bunig uchun qo’shimcha d[] massivini kiritamiz. Dastlabki uch uchun d[v] = 0. Navbatdan olingan har bir v uchni oladigan bo’lsak, unga qo’shni bo’lgan hali ko’rilmagan u uchga yana bitta qirra orqali o’tib borish kerak. Shuning uchun d[u] = d[v]+1 qilib belgilab qo’yamiz.
Yuqoridagi graf uchun eng qisqa masofalar quyidagicha bo’ladi:
Masalalar.
4-topshiriq
Vladislav Isenbaev is a two-time champion of Ural, vice champion of TopCoder Open 2009, and absolute champion of ACM ICPC 2009. In the time you will spend reading this problem statement Vladislav would have solved a problem. Maybe, even two…
Since Vladislav Isenbaev graduated from the Specialized Educational and Scientific Center at Ural State University, many of the former and present contestants at USU have known him for quite a few years. Some of them are proud to say that they either played in the same team with him or played in the same team with one of his teammates…
Let us define Isenbaev's number as follows. This number for Vladislav himself is 0. For people who played in the same team with him, the number is 1. For people who weren't his teammates but played in the same team with one or more of his teammates, the number is 2, and so on. Your task is to automate the process of calculating Isenbaev's numbers so that each contestant at USU would know their proximity to the ACM ICPC champion.
Input
The first line contains the number of teams n (1 ≤ n ≤ 100). In each of the following n lines you are given the names of the three members of the corresponding team. The names are separated with a space. Each name is a nonempty line consisting of English letters, and its length is at most 20 symbols. The first letter of a name is capital and the other letters are lowercase.
Output
For each contestant mentioned in the input data output a line with their name and Isenbaev's number. If the number is undefined, output “undefined” instead of it. The contestants must be ordered lexicographically.
Sample
Input
|
Output
|
7
Isenbaev Oparin Toropov
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Fominykh Isenbaev Oparin
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
|
Ayzenshteyn 2
Burmistrov 3
Chevdar 3
Cormen undefined
Dublennykh 2
Fominykh 1
Isenbaev 0
Ivankov 2
Kurpilyanskiy 3
Leiserson undefined
Oparin 1
Rivest undefined
Samsonov 2
Toropov 1
|
#include
#include
#include
#include
#include
using namespace std;
map id;
vector adj[300];
int dist[300];
void bfs(){
int Q[300],head = 0,tail = 0;
memset(dist,-1,sizeof(dist));
if(id.find("Isenbaev") != id.end()){
int s = id["Isenbaev"];
dist[s] = 0;
Q[tail] = s;
++tail;
while(head < tail){
int cur = Q[head];
++head;
for(int i = adj[cur].size()-1;i >= 0;--i){
int nxt = adj[cur][i];
if(dist[nxt] == -1){
dist[nxt] = dist[cur] + 1;
Q[tail] = nxt;
++tail;}
}
}
}
}
int main(){
int N;
cin >> N;
int V = 0;
string s1,s2,s3;
for(int i = 0;i < N;++i){
cin >> s1 >> s2 >> s3;
if(id.find(s1) == id.end()) id[s1] = V++;
if(id.find(s2) == id.end()) id[s2] = V++;
if(id.find(s3) == id.end()) id[s3] = V++;
int a = id[s1],b = id[s2],c = id[s3];
adj[a].push_back(b); adj[a].push_back(c);
adj[b].push_back(a); adj[b].push_back(c);
adj[c].push_back(a); adj[c].push_back(b);
}
bfs();
for(map::iterator it = id.begin();it != id.end();++it){
cout << it->first << " ";
if(dist[it->second] == -1) cout << "undefined" << endl;
else cout << dist[it->second] << endl; }
return 0;
}
