Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<fstream>
- using namespace std;
- //алгоритм обхода в глубину, суть его в том, что мы начнаем с какой-то вершинкой и далее переходим во все вершины смежные с ней
- // и таким образом он проходит по всему графу и помечает вершины в массиве used которые посетил как true, чтобы второй раз в них не заходить
- void DFS(int v, vector<vector<int>> &e,vector<bool> &used)
- {
- used[v] = true;
- for (int i = 0; i < e[v].size(); i++)
- {
- int tek = e[v][i];
- if (!used[tek])
- DFS(tek, e, used);
- }
- }
- // будем исходить из определения - компонентой связанности называется такое множество вершин, что мы из каждой можем добраться в каждую
- // DFS он проходит по всем вершинам до которых есть путь из вершины i , тем самым он за один проход выделить компненту связанности
- // далее нам нужно запуститься из всех вершин до которых DFS не смог дойти в первый раз и т.д.
- int CountComponents(vector<vector<int>> &e, vector<bool> &used, int n)
- {
- int count = 0;
- for (int i = 0; i < n; i++) // идем по всем вершинам и пооочереди запускаемся из них DFS'ом при этом проверяя, посещали ли мы ее уже
- { // если посещали, то значит она относится к какой-то компоненте связанности и от нее не нужно запускаться
- // а если не посещали, то значит есть еще 1 компонента связанности поэтому мы увеличиваем ответ на 1
- // и снова запускаемся и т.д
- if (!used[i])
- {
- DFS(i, e, used);
- count++;
- }
- }
- return count;
- }
- int main()
- {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- int n;
- fin >> n;
- vector<vector<int>> e(n); // список смежности
- vector<bool>used(n, false); // массив в котором true если мы эту вершинку посетили, иначе false
- for (int i = 0;i<n;i++) //вводим из матрицы смежности сразу в список смежности для того чтобы было удобнее работать
- for (int j = 0; j < n; j++)
- {
- int x;
- fin >> x;
- if (x)
- e[i].push_back(j);
- }
- fout << CountComponents(e, used, n);
- fin.close();
- fout.close();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement