Подсчет количества узлов в каждой соединенной части неориентированного невзвешенного графа
Я новичок в C ++ STL и недавно начал Теорию графов.
После обращения к https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/, Я могу подсчитать количество подключенных компонентов в неориентированном невзвешенном графике, используя DFS как:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int connected=0, temp1, temp2,n, p;
void DFS(int start, vector<int> v[],vector<int> &visited) {
visited[start] = 1;
for(int i= 0; i<v[start].size(); ++i) {
if(visited[v[start][i]] == 0)
DFS(v[start][i], v, visited);
}
}
int main() {
cin>>n>>p; // number of vertices and edges
vector<int> v[n+1], visited(n+1,0);
for(int i=0; i<p; ++i) {
cin>>temp1>>temp2;
v[temp1].push_back(temp2);
v[temp2].push_back(temp1);
}
connected = 0;
for(int i=1;i<=n;++i) {
if(visited[i] == 0 ) {
connected++;
DFS(i,v,visited);
}
}
cout<<connected<<endl;
return 0;
}
Но как нам подсчитать общее количество узлов в каждом компоненте?
Например: на этом графике увидеть изображение Есть 3 подключенных
компоненты, с нет. узлов 3, 2 и 1 соответственно.
Решение
Вы могли бы поддерживать фиктивную переменную count с каждым звонком DFS от main()
void DFS(int start, vector<int> v[],vector<int> &visited, int &count)
{
visited[start] = 1;
count++;
for(int i= 0; i<v[start].size(); ++i)
{
if(visited[v[start][i]] == 0)
DFS(v[start][i], v, visited);
}
}
а также
for(int i=1;i<=n;++i)
{
if(visited[i] == 0 )
{
connected++;
int count=0;
DFS(i,v,visited,count);
cout<<"This component has "<<count<<" nodes"<<"\n";
}
}
Или вы можете сослаться на изменение в visited вектор (количество новых 1 в нем) после каждого вызова DFS() от main()
Другие решения
Вы можете поддерживать глобальную переменную no_of_nodes который будет установлен в ноль в начале dfs каждого компонента и увеличен на единицу при посещении каждого узла в этом компоненте.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int connected=0, temp1, temp2,n, p;
int no_of_nodes=0;void DFS(int start, vector<int> v[],vector<int> &visited) {
visited[start] = 1;
no_of_nodes++;
for(int i= 0; i<v[start].size(); ++i) {
if(visited[v[start][i]] == 0)
DFS(v[start][i], v, visited);
}
}
int main() {
cin>>n>>p; // number of vertices and edges
vector<int> v[n+1], visited(n+1,0);
for(int i=0; i<p; ++i) {
cin>>temp1>>temp2;
v[temp1].push_back(temp2);
v[temp2].push_back(temp1);
}
connected = 0;
vector<int>nodes;
for(int i=1;i<=n;++i) {
if(visited[i] == 0 ) {
connected++;
no_of_nodes=0;
DFS(i,v,visited);
nodes.push_back(no_of_nodes);
}
}
cout<<connected<<endl;
return 0;
}