fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(a) (a).begin(), (a).end()
  4. #define dbg_line(x) cout << (x) << '\n'
  5. #define dbg(x) cout << x << " "
  6.  
  7. using namespace std;
  8.  
  9. // <--> Report constants <-->
  10.  
  11. typedef pair<int, int> pii;
  12. const int max_n = 1e5 + 5;
  13. const ll inf = 1e9;
  14. const ll m_inf = -1e9;
  15. const ll mod = 1e9 + 7;
  16.  
  17. // <--> Report variables <-->
  18.  
  19. unordered_map<string, int> NametoNum;
  20. unordered_map<int, string> NumtoName;
  21. vector<int> adj[30];
  22. int n, m, cnt, timer = 0;
  23. int low[max_n], disc[max_n];
  24. stack<int> st;
  25. vector<vector<string>> res;
  26. bool visited[max_n];
  27.  
  28. // <--> Main Code is Here <-->
  29.  
  30. void setIO(){
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(NULL);
  33.     cout.tie(NULL);
  34. }
  35.  
  36. void call_file(){
  37.     freopen("input.txt","r",stdin);
  38.     freopen("output.txt","w",stdout);
  39. }
  40.  
  41. void tarjan(int u){
  42.     visited[u] = true;
  43.     low[u] = disc[u] = timer++;
  44.     st.push(u);
  45.     for (int v : adj[u]){
  46.         if (!visited[v]){
  47.             tarjan(v);
  48.             low[u] = min(low[u], low[v]);
  49.         }
  50.         else{
  51.             low[u] = min(low[u], disc[v]);
  52.         }
  53.     }
  54.     if (low[u] == disc[u]){
  55.         vector<string> tmp;
  56.         while(st.top() != u){
  57.             tmp.push_back(NumtoName[st.top()]);
  58.             st.pop();
  59.         }
  60.         tmp.push_back(NumtoName[st.top()]);
  61.         st.pop();
  62.         res.push_back(tmp);
  63.     }
  64. }
  65.  
  66. int main(){
  67.     setIO();
  68.     call_file();
  69.     int setID = 0;
  70.     while(cin >> n >> m){
  71.         if ((n + m) == 0){
  72.             break;
  73.         }
  74.         NametoNum.clear();
  75.         NumtoName.clear();
  76.         res.clear();
  77.         timer = 0;
  78.         cnt = 0;
  79.         for (int i = 0; i < 30; i++){
  80.             adj[i].clear();
  81.         }
  82.         memset(disc, 0, sizeof(disc));
  83.         memset(low, 0, sizeof(low));
  84.         memset(visited, false, sizeof(visited));
  85.         while(!st.empty()){
  86.             st.pop();
  87.         }
  88.         for (int i = 0; i < m; i++){
  89.             string caller, receiver;
  90.             cin >> caller >> receiver;
  91.             if (NametoNum.find(caller) == NametoNum.end()){
  92.                 NametoNum[caller] = cnt;
  93.                 NumtoName[cnt] = caller;
  94.                 cnt++;
  95.             }
  96.             if (NametoNum.find(receiver) == NametoNum.end()){
  97.                 NametoNum[receiver] = cnt;
  98.                 NumtoName[cnt] = receiver;
  99.                 cnt++;
  100.             }
  101.             int u = NametoNum[caller], v = NametoNum[receiver];
  102.             adj[u].push_back(v);
  103.         }
  104.         cout << "Calling circles for data set " << ++setID << ":" << '\n';
  105.         for (int j = 0; j < n; j++){
  106.             if (!visited[j]){
  107.                 tarjan(j);
  108.             }
  109.         }
  110.         for (auto scc : res){
  111.             for (int k = 0; k < scc.size(); k++){
  112.                 cout << scc[k];
  113.                 if (k != scc.size() - 1) cout << ", ";
  114.             }
  115.             cout << '\n';
  116.         }
  117.         cout << '\n';
  118.     }
  119. }
  120.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oU82aZ
language:
C++ (gcc 8.3)
created:
11 days 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!