Нахождение фундаментальной системы циклов в графе
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int n, m, x, y;
vector<vector<int>> g;
vector<bool> used;
vector<int> comp;
vector<int> index;
void DFS(int v)
{
used[v] = true;
comp.push_back(v);
for (int i = 0; i < g[v].size(); ++i)
{
int to = g[v][i];
if (!used[to])
DFS(to);
}
}
int main()
{
setlocale(LC_ALL, "");
int count=0;
ifstream in("input1.txt");
in >> n;
n++;
in >> m;
used.resize(n);
g.resize(n);
for (int i = 0; i < m; i++)
{
in >> x >> y;
index.push_back(x);// запись в index всех координат
index.push_back(y);// и по x и по y
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0; i < used.size(); i++)
used[i] = false; // сброс флагов
for (int i = 0; i < used.size(); i++)
if (!used[index[i]]) // проверка флагов
{
comp.clear();
DFS(index[i]); // передача значения координаты с порядковым номером от от 0 до значение последней координаты + 1
cout << "Компоненты:";
for (int j = 0; j < comp.size(); j++)
cout << ' ' << comp[j];
cout << endl;
count++;
}
cout <<"Количество независимых циклов: "<< m-n + count << endl;
in.close();
system("pause");
return 0;
}
Граф в файле:
5 //кол-во вершин
7 //кол-во ребер
1 2 // дуги
1 3
1 4
1 5
2 3
2 4
2 5
Пытаюсь найти ФСР графа(количество всех независимых циклов). У меня не получается. Просто выводит 1,2,3,4,5. В этом графе 4 независимых цикла. Должно выводить 4 компоненты и число 4. Например,на таком графе нормально выводит:
7
5
1 2
2 3
3 4
5 6
6 7