#include <cstdlib> #include <cstdio> #include <iostream> #include <sstream> #include <cstring> #include <string> #include <utility> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <functional> #include <bitset> using namespace std; int main() { int v, e; bitset < 26 > edges; char x, y; char a[100]; int t; scanf("%d\n", &t); while (t--) { v = 0, e = 0; while (gets(a), a[0] != '*') { e++; // total no of edges in the graph sscanf(a, "(%c,%c)", &x, &y); /* marking all the verices with at least one edge*/ edges.set((x - 'A')); edges.set((y - 'A')); } int connected_vertices = edges.count(); // no of set bits gets(a); string line(a); v = count(line.begin(), line.end(), ',') + 1; // total no of vertices in the graph // no of connected components in a graph =v-e int acron = v - connected_vertices; // no of acrons= total vertices - (connected_vertices) int tree = v - e - acron; printf("There are %d tree(s) and %d acron(s).\n", tree, acron); edges.reset(); } return 0; }
2 (A,B) (B,C) (B,D) (D,E) (E,F) (B,G) (G,H) (G,I) (J,K) (K,L) (K,M) **** A,B,C,D,E,F,G,H,I,J,K,L,M,N (A,B) (A,C) (C,F) ** A,B,C,D,F