fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define UNVISITED -1
  6.  
  7. struct caller_t: set< int >
  8. {
  9.     string name; bool visited; int least, rank;
  10.  
  11.     caller_t( const string& s ) :
  12.         name( s ), visited( false ), least( UNVISITED ), rank( UNVISITED ) {}
  13.  
  14.     void update_least( int least_v )
  15.     {
  16.         least = min( least, least_v );
  17.     }
  18.  
  19.     bool calling_circle() const
  20.     {
  21.         return least == rank;
  22.     }
  23.  
  24.     void visit( int u )
  25.     {
  26.         least = rank = u, visited = true;
  27.     }
  28.  
  29.     void write()
  30.     {
  31.         cout << name, visited = false;
  32.     }
  33. };
  34.  
  35. typedef vector< caller_t > callers_t;
  36.  
  37. struct used_names_t: map< string, int >
  38. {
  39.     int read( callers_t& callers )
  40.     {
  41.         string name; cin >> name;
  42.  
  43.         auto it = find( name ); int index = size();
  44.  
  45.         if ( it != end() )
  46.             index = it->second;
  47.         else
  48.             emplace( name, index ), callers.emplace_back( name );
  49.  
  50.         return index;
  51.     }
  52. };
  53.  
  54. struct calling_circle_t: stack< int >
  55. {
  56.     void write( callers_t& s, int u )
  57.     {
  58.         for( int v; ( s[ v = top() ].write(), pop(), v ) != u; cout << ", " );
  59.  
  60.         cout << '\n';
  61.     }
  62. };
  63.  
  64. struct data_set: callers_t
  65. {
  66.     used_names_t used_names; int visited; calling_circle_t calling_circle;
  67.  
  68.     data_set() : visited( 0 ) {}
  69.  
  70.     void phone_call()
  71.     {
  72.         int caller = used_names.read( *this ),
  73.             called = used_names.read( *this );
  74.  
  75.         at( caller ).insert( called );
  76.     }
  77.  
  78.     void dfs( int u )
  79.     {
  80.         at( u ).visit( visited++ ), calling_circle.push( u );
  81.  
  82.         for( auto v: at( u ) )
  83.         {
  84.             if ( at( v ).rank == UNVISITED )
  85.                 dfs( v );
  86.  
  87.             if ( at( v ).visited )
  88.                 at( u ).update_least( at( v ).least );
  89.         }
  90.  
  91.         if ( at( u ).calling_circle() )
  92.             calling_circle.write( *this, u );
  93.     }
  94. };
  95.  
  96. int main()
  97. {
  98.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  99.  
  100.     for( int test = 1; ; test++ )
  101.     {
  102.         int n, m; cin >> n >> m;
  103.  
  104.         if ( n == 0 and m == 0 )
  105.             return 0;
  106.  
  107.         data_set s;
  108.  
  109.         for( int i = 0; i < m; i++ )
  110.             s.phone_call();
  111.  
  112.         if ( test > 1 )
  113.             cout << '\n';
  114.  
  115.         cout << "Calling circles for data set " << test << ':' << '\n';
  116.  
  117.         for( int i = 0; i < n; i++ )
  118.             if ( s[ i ].rank == UNVISITED )
  119.                 s.dfs( i );
  120.     }
  121. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
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
copy 
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/s4OBdO
Calling Circles
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!