fork(1) download 
  1. #include <bits/stdc++.h>
  2. #define vi vector<int>
  3. #define vvi vector<vi>
  4. #define pb push_back
  5. #define mp map<string, int>
  6. #define ii pair<int , int>
  7. #define vii vector<ii>
  8. #define MAX 30
  9. #define UNVISITED -1
  10. #define rep(i, n) for (int i = 0; i < (int)n; i++)
  11. #define rep1(i, n) for (int i = 1; i <= (int)n; i++)
  12.  
  13. using namespace std;
  14.  
  15. vvi adj(MAX);
  16. int dfs_num[MAX], dfs_low[MAX], visited[MAX];
  17. mp store;
  18. stack<int> st;
  19. vvi components(MAX);
  20. vector<string> names;
  21. int n, m, dfsCounter, globalIndex;
  22.  
  23. void dfs(int u)
  24. {
  25.     dfs_num[u] = dfs_low[u] = dfsCounter++;
  26.     visited[u] = 1;
  27.     st.push(u);
  28.     rep(i, adj[u].size())
  29.     {
  30.         int v = adj[u][i];
  31.         if (dfs_num[v] == UNVISITED)
  32.             dfs(v);
  33.         if (visited[v])
  34.             dfs_low[u] = min(dfs_low[u], dfs_low[v]);
  35.     }
  36.     if (dfs_num[u] == dfs_low[u])
  37.     {
  38.         while (1)
  39.         {
  40.             int vertex = st.top();
  41.             visited[vertex] = 0;
  42.             st.pop();
  43.             if (u == vertex)
  44.             {
  45.                 printf("%s\n", names[vertex-1].c_str());
  46.                 break;
  47.             }
  48.             else
  49.                 printf("%s, ", names[vertex-1].c_str());
  50.         }
  51.     }
  52. }
  53.  
  54. void clear()
  55. {
  56.     memset(dfs_num, UNVISITED, sizeof dfs_num);
  57.     memset(dfs_low, UNVISITED, sizeof dfs_low);
  58.     memset(visited, 0, sizeof visited);
  59.     rep(i, n)
  60.     {
  61.         adj[i].clear();
  62.     }
  63.     names.clear();
  64.     while (!st.empty())
  65.         st.pop();
  66.     store.clear();
  67.     dfsCounter = 0;
  68.     globalIndex = 0;
  69. }
  70.  
  71. int main()
  72. {
  73.     int test = 0;
  74.     int blank = 0;
  75.     while (scanf("%d %d", &n, &m))
  76.     {
  77.         if (!n && !m)
  78.             break;
  79.         if (blank)
  80.             printf("\n");
  81.         blank = 1;
  82.         clear();
  83.         int index = 1;
  84.         rep(i, m)
  85.         {
  86.             string s1, s2;
  87.             cin >> s1 >> s2;
  88.             if (store[s1] == 0)
  89.             {
  90.                 store[s1] = index++;
  91.                 names.pb(s1);
  92.             }
  93.             if (store[s2] == 0)
  94.             {
  95.                 store[s2] = index++;
  96.                 names.pb(s2);
  97.             }
  98.             adj[store[s1]].pb(store[s2]);
  99.         }
  100.         printf("Calling circles for data set %d:\n", ++test);
  101.         rep1(i, n)
  102.         {
  103.             if (dfs_num[i] == UNVISITED)
  104.                 dfs(i);
  105.         }
  106.     }
  107. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
5 6
Ben Alexander
Alexander Dolly
Dolly Ben
Dolly Benedict
Benedict Dolly
Alexander Aaron
14 34
John Aaron
Aaron Benedict
Betsy John
Betsy Ringo
Ringo Dolly
Benedict Paul
John Betsy
John Aaron
Benedict George
Dolly Ringo
Paul Martha
George Ben
Alexander George
Betsy Ringo
Alexander Stephen
Martha Stephen
Benedict Alexander
Stephen Paul
Betsy Ringo
Quincy Martha
Ben Patrick
Betsy Ringo
Patrick Stephen
Paul Alexander
Patrick Ben
Stephen Quincy
Ringo Betsy
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Quincy Martha
0 0
stdout 
Calling circles for data set 1:
Aaron
Benedict, Dolly, Alexander, Ben

Calling circles for data set 2:
Patrick, Ben, George, Alexander, Quincy, Stephen, Martha, Paul
Benedict
Aaron
Dolly, Ringo, Betsy, John
https://ideone.com/5kw603
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!