Dados n amigos y sus relaciones de amistad, encuentre el número total de grupos que existen. Y la cantidad de formas de nuevos grupos que se pueden formar compuestos por personas de cada grupo existente.
Si no se da ninguna relación para ninguna persona, entonces esa persona no tiene grupo y singularmente forma un grupo. Si a es amigo de b y b es amigo de c, entonces ab y c forman un grupo.
Ejemplos:
Input : Number of people = 6
Relations : 1 - 2, 3 - 4
and 5 - 6
Output: Number of existing Groups = 3
Number of new groups that can
be formed = 8
Explanation: The existing groups are
(1, 2), (3, 4), (5, 6). The new 8 groups
that can be formed by considering a
member of every group are (1, 3, 5),
(1, 3, 6), (1, 4, 5), (1, 4, 6), (2,
3, 5), (2, 3, 6), (2, 4, 5) and (2, 4,
6).
Input: Number of people = 4
Relations : 1 - 2 and 2 - 3
Output: Number of existing Groups = 2
Number of new groups that can
be formed = 3
Explanation: The existing groups are
(1, 2, 3) and (4). The new groups that
can be formed by considering a member
of every group are (1, 4), (2, 4), (3, 4).
Para contar el número de grupos, simplemente necesitamos contar los componentes conectados en el gráfico no dirigido dado . El conteo de componentes conectados se puede hacer fácilmente usando DFS o BFS . Dado que este es un gráfico no dirigido, la cantidad de veces que una búsqueda en profundidad comienza desde un vértice no visitado para cada amigo es igual a la cantidad de grupos formados.
Para contar el número de formas en que formamos nuevos grupos se puede hacer usando simplemente la fórmula que es (N1)*(N2)*….(Nn) donde Ni es el número de personas en el i-ésimo grupo.
Implementación:
C++
// C++ program to count number of existing
// groups and number of new groups that can
// be formed.
#include <bits/stdc++.h>
using namespace std;
class Graph {
int V; // No. of vertices
// Pointer to an array containing
// adjacency lists
list<int>* adj;
int countUtil(int v, bool visited[]);
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addRelation(int v, int w);
void countGroups();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// Adds a relation as a two way edge of
// undirected graph.
void Graph::addRelation(int v, int w)
{
// Since indexing is 0 based, reducing
// edge numbers by 1.
v--;
w--;
adj[v].push_back(w);
adj[w].push_back(v);
}
// Returns count of not visited nodes reachable
// from v using DFS.
int Graph::countUtil(int v, bool visited[])
{
int count = 1;
visited[v] = true;
for (auto i=adj[v].begin(); i!=adj[v].end(); ++i)
if (!visited[*i])
count = count + countUtil(*i, visited);
return count;
}
// A DFS based function to Count number of
// existing groups and number of new groups
// that can be formed using a member of
// every group.
void Graph::countGroups()
{
// Mark all the vertices as not visited
bool* visited = new bool[V];
memset(visited, 0, V*sizeof(int));
int existing_groups = 0, new_groups = 1;
for (int i = 0; i < V; i++)
{
// If not in any group.
if (visited[i] == false)
{
existing_groups++;
// Number of new groups that
// can be formed.
new_groups = new_groups *
countUtil(i, visited);
}
}
if (existing_groups == 1)
new_groups = 0;
cout << "No. of existing groups are "
<< existing_groups << endl;
cout << "No. of new groups that can be"
" formed are " << new_groups
<< endl;
}
// Driver code
int main()
{
int n = 6;
// Create a graph given in the above diagram
Graph g(n); // total 6 people
g.addRelation(1, 2); // 1 and 2 are friends
g.addRelation(3, 4); // 3 and 4 are friends
g.addRelation(5, 6); // 5 and 6 are friends
g.countGroups();
return 0;
}
Java
// Java program to count number of
// existing groups and number of
// new groups that can be formed.
import java.util.*;
import java.io.*;
class Graph{
// No. of vertices
private int V;
// Array of lists for Adjacency
// List Representation
private LinkedList<Integer> adj[];
// Constructor
@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
adj = new LinkedList[V];
for(int i = 0; i < V; i++)
{
adj[i] = new LinkedList();
}
}
// Adds a relation as a two way edge of
// undirected graph.
public void addRelation(int v, int w)
{
// Since indexing is 0 based, reducing
// edge numbers by 1.
v--;
w--;
adj[v].add(w);
adj[w].add(v);
}
// Returns count of not visited nodes
// reachable from v using DFS.
int countUtil(int v, boolean visited[])
{
int count = 1;
visited[v] = true;
// Recur for all the vertices adjacent
// to this vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
count = count + countUtil(n, visited);
}
return count;
}
// A DFS based function to Count number of
// existing groups and number of new groups
// that can be formed using a member of
// every group.
void countGroups()
{
// Mark all the vertices as not
// visited(set as false by default
// in java)
boolean visited[] = new boolean[V];
int existing_groups = 0, new_groups = 1;
for(int i = 0; i < V; i++)
{
// If not in any group.
if (visited[i] == false)
{
existing_groups++;
// Number of new groups that
// can be formed.
new_groups = new_groups *
countUtil(i, visited);
}
}
if (existing_groups == 1)
new_groups = 0;
System.out.println("No. of existing groups are " +
existing_groups);
System.out.println("No. of new groups that " +
"can be formed are " +
new_groups);
}
// Driver code
public static void main(String[] args)
{
int n = 6;
// Create a graph given in
// the above diagram
Graph g = new Graph(n); // total 6 people
g.addRelation(1, 2); // 1 and 2 are friends
g.addRelation(3, 4); // 3 and 4 are friends
g.addRelation(5, 6); // 5 and 6 are friends
g.countGroups();
}
}
// This code is contributed by MuskanKalra1
Python3
# Python3 program to count number of
# existing groups and number of new
# groups that can be formed.
class Graph:
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
# Adds a relation as a two way
# edge of undirected graph.
def addRelation(self, v, w):
# Since indexing is 0 based,
# reducing edge numbers by 1.
v -= 1
w -= 1
self.adj[v].append(w)
self.adj[w].append(v)
# Returns count of not visited
# nodes reachable from v using DFS.
def countUtil(self, v, visited):
count = 1
visited[v] = True
i = 0
while i != len(self.adj[v]):
if (not visited[self.adj[v][i]]):
count = count + self.countUtil(self.adj[v][i],
visited)
i += 1
return count
# A DFS based function to Count number
# of existing groups and number of new
# groups that can be formed using a
# member of every group.
def countGroups(self):
# Mark all the vertices as
# not visited
visited = [0] * self.V
existing_groups = 0
new_groups = 1
for i in range(self.V):
# If not in any group.
if (visited[i] == False):
existing_groups += 1
# Number of new groups that
# can be formed.
new_groups = (new_groups *
self.countUtil(i, visited))
if (existing_groups == 1):
new_groups = 0
print("No. of existing groups are",
existing_groups)
print("No. of new groups that",
"can be formed are", new_groups)
# Driver code
if __name__ == '__main__':
n = 6
# Create a graph given in the above diagram
g = Graph(n) # total 6 people
g.addRelation(1, 2) # 1 and 2 are friends
g.addRelation(3, 4) # 3 and 4 are friends
g.addRelation(5, 6) # 5 and 6 are friends
g.countGroups()
# This code is contributed by PranchalK
Producción
No. of existing groups are 3 No. of new groups that can be formed are 8
Complejidad temporal: O(N + R) donde N es el número de personas y R es el número de relaciones.
Este artículo es una contribución de Raj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA