fork(3) download
  1. #include <cstdlib>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <sstream>
  5. #include <cstring>
  6. #include <string>
  7. #include <utility>
  8. #include <stack>
  9. #include <queue>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <functional>
  13. #include <bitset>
  14.  
  15. using namespace std;
  16.  
  17. int main() {
  18. int v, e;
  19. bitset < 26 > edges;
  20. char x, y;
  21. char a[100];
  22. int t;
  23. scanf("%d\n", &t);
  24. while (t--) {
  25. v = 0, e = 0;
  26. while (gets(a), a[0] != '*') {
  27. e++; // total no of edges in the graph
  28. sscanf(a, "(%c,%c)", &x, &y);
  29. /* marking all the verices with at least one edge*/
  30. edges.set((x - 'A'));
  31. edges.set((y - 'A'));
  32. }
  33. int connected_vertices = edges.count(); // no of set bits
  34. gets(a);
  35. string line(a);
  36. v = count(line.begin(), line.end(), ',') + 1; // total no of vertices in the graph
  37. // no of connected components in a graph =v-e
  38. int acron = v - connected_vertices; // no of acrons= total vertices - (connected_vertices)
  39. int tree = v - e - acron;
  40. printf("There are %d tree(s) and %d acron(s).\n", tree, acron);
  41. edges.reset();
  42. }
  43. return 0;
  44. }
  45.  
  46.  
Success #stdin #stdout 0s 3476KB
stdin
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
stdout
There are 2 tree(s) and 1 acron(s).
There are 1 tree(s) and 1 acron(s).