Conte o Número de Estrelas em um Grafo
Dado um grafo não dirigido com
v vértices e e arestas, é solicitado que você calcule quantos grafos do tipo “estrela” ele contém.Um grafo estrela é definido por ter um vértice central conectado a todos os demais vértices, enquanto esses outros vértices se conectam apenas ao vértice central e não entre si.
Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 1000) e e (1 ≤ e ≤ 10 000).As próximas
e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), que representam uma aresta entre v1 e v2.Saída
O programa deve imprimir a quantidade de grafos estrela encontrados no grafo fornecido.
Exemplos
Input | Output |
7 6
1 5
2 5
3 5
7 5
6 5
4 5 | 1 |
8 7
1 5
2 5
3 5
7 5
6 5
4 5
1 8 | 0 |
8 6
1 2
2 3
4 2
5 6
7 6
8 6 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB