Skip to content

Commit c79d2da

Browse files
rudi8848rudi8848
committed
dfs, bfs
1 parent 507b5ca commit c79d2da

2 files changed

Lines changed: 206 additions & 0 deletions

File tree

‎bfs.cpp‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
#include <iostream>
2+
#include <vector>
3+
#include <queue>
4+
5+
/*
6+
На вход программе подаётся описание простого связного графа. Первая строка содержит два числа:
7+
число вершин V≤10000 и число рёбер E≤30000 графа. Следующие E строк содержат номера пар вершин,
8+
соединенных рёбрами. Вершины имеют номера от 0 до V−1. Выведите список из V чисел — расстояний
9+
от вершины 0 до соответствующих вершин графа.
10+
11+
Sample Input:
12+
13+
6 7
14+
0 1
15+
1 2
16+
2 0
17+
3 2
18+
4 3
19+
4 2
20+
5 4
21+
Sample Output:
22+
23+
0 1 1 2 2 3
24+
*/
25+
void bfs(std::vector<std::vector<int>> &list, int v, int e)
26+
{
27+
std::vector<bool> marked(v);
28+
std::vector<int> distance(v);
29+
std::vector<int> path(v);
30+
std::queue<int> q;
31+
int cur = 0;
32+
33+
for (auto i : marked)
34+
i = false;
35+
for (auto i : distance)
36+
i = 0;
37+
q.push(cur);
38+
marked[cur] = true;
39+
distance[cur] = 0;
40+
path[cur] = -1;
41+
42+
while (!q.empty())
43+
{
44+
cur = q.front();
45+
q.pop();
46+
for ( int j = 0; j < list.size(); ++j)
47+
{
48+
int point = -1;
49+
if (list[j][0] == cur)
50+
point = list[j][1];
51+
else if (list[j][1] == cur)
52+
point = list[j][0];
53+
54+
if (point >= 0 && !marked[point])
55+
{
56+
q.push(point);
57+
distance[point] = distance[cur] + 1;
58+
marked[point] = true;
59+
path[point] = cur;
60+
}
61+
}
62+
}
63+
for (int i : distance)
64+
std::cout << i << std::endl;
65+
/*
66+
//find path to 4
67+
int f = 4;
68+
if(!marked[f])
69+
std::cout << "No path" << std::endl;
70+
else
71+
{
72+
std::vector <int> way;
73+
for (int p = f; p != -1; p = path[p])
74+
way.push_back(p);
75+
std::cout << "Path to " << f << std::endl;
76+
for (int k : way)
77+
std::cout << k << std::endl;
78+
}
79+
*/
80+
}
81+
82+
int main(void)
83+
{
84+
int v = 0;
85+
int e = 0;
86+
87+
std::cin >> v >> e;
88+
if (v < 0 || e < 0)
89+
return 1;
90+
else if (v == 0 || e == 0)
91+
{
92+
std::cout << v << std::endl;
93+
return 0;
94+
}
95+
std::vector < std::vector<int> > g;
96+
for (int j = 0; j < e; ++j)
97+
{
98+
int a, b;
99+
std::cin >> a >> b;
100+
g.push_back(std::vector<int>({a, b}));
101+
}
102+
bfs(g, v, e);
103+
return 0;
104+
}

‎dfs.cpp‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
#include <iostream>
2+
#include <vector>
3+
4+
/*
5+
Найти количество компонент связности неориентированного графа при помощи поиска в глубину.
6+
7+
Формат входных данных:
8+
На вход подаётся описание графа. В первой строке указаны два натуральных числа, разделенные
9+
пробелом: число вершин v≤1000 и число рёбер e≤1000. В следующих e строках содержатся описания
10+
рёбер. Каждое ребро задаётся разделённой пробелом парой номеров вершин, которые это ребро
11+
соединяет. Считается, что вершины графа пронумерованы числами от 1 до v.
12+
13+
Формат выходных данных:
14+
15+
Одно число — количество компонент связности графа.
16+
17+
Sample Input 1:
18+
19+
4 2
20+
1 2
21+
3 2
22+
Sample Output 1:
23+
24+
2
25+
Sample Input 2:
26+
27+
4 3
28+
1 2
29+
3 2
30+
4 3
31+
Sample Output 2:
32+
33+
1
34+
*/
35+
void dfs(int i, std::vector<bool> &v, int adj[][2], int max)
36+
{
37+
38+
v[i] = true;
39+
40+
for (int j = 1; j < max; ++j)
41+
{
42+
if (adj[j][0] == adj[j][1] && adj[j][1] == i)
43+
return ;
44+
if (adj[j][0] == i || adj[j][1] == i)
45+
{
46+
if (!v[adj[j][0]])
47+
dfs(adj[j][0], v, adj, max);
48+
else if (!v[adj[j][1]])
49+
dfs(adj[j][1], v, adj, max);
50+
}
51+
}
52+
}
53+
54+
int main(void)
55+
{
56+
int v = 0;
57+
int e = 0;
58+
59+
std::cin >> v >> e;
60+
if (v < 0 || e < 0)
61+
return 1;
62+
else if (v == 0 || e == 0)
63+
{
64+
std::cout << v << std::endl;
65+
return 0;
66+
}
67+
++v;
68+
++e;
69+
70+
std::vector<bool> ver(v);
71+
72+
for (bool i : ver)
73+
i = false;
74+
75+
int adj[e][2];
76+
77+
adj[0][0] = 0;
78+
adj[0][1] = 0;
79+
for (int j = 1; j < e; ++j)
80+
std::cin >> adj[j][0] >> adj[j][1];
81+
82+
int res = 0;
83+
int j = 1;
84+
while (j < ver.size())
85+
{
86+
if (j < ver.size() && ver[j])
87+
{
88+
while (j < ver.size() && ver[j])
89+
++j;
90+
++res;
91+
}
92+
else/*if (j < ver.size() && !ver[j])*/
93+
{
94+
dfs(j, ver, adj, e);
95+
while (j < ver.size() && ver[j])
96+
++j;
97+
++res;
98+
}
99+
}
100+
std::cout << res << std::endl;
101+
return 0;
102+
}

0 commit comments

Comments
 (0)