fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define F first
  5. #define S second
  6. #define all(x) x.begin(),x.end()
  7. #define pii pair<int,int>
  8. #define pb push_back
  9. #define sz(x) (int)(x.size())
  10. #define chmin(x,y) x=min(x,y)
  11. #define chmax(x,y) x=max(x,y)
  12. #define vi vector<int>
  13. #define vp vector<pii>
  14. #define vvi vector<vi>
  15. #define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
  16. #define __lg(x) 63-__builtin_clzll(x)
  17. #define pow2(x) (1LL<<x)
  18. void __print(int x) {cerr << x;}
  19. void __print(float x) {cerr << x;}
  20. void __print(double x) {cerr << x;}
  21. void __print(long double x) {cerr << x;}
  22. void __print(char x) {cerr << '\'' << x << '\'';}
  23. void __print(const char *x) {cerr << '\"' << x << '\"';}
  24. void __print(const string &x) {cerr << '\"' << x << '\"';}
  25. void __print(bool x) {cerr << (x ? "true" : "false");}
  26.  
  27. template<typename T, typename V>
  28. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  29. template<typename T>
  30. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  31. void _print() {cerr << "]\n";}
  32. template <typename T, typename... V>
  33. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  34. #ifdef local
  35. void CHECK();
  36. void setio(){
  37.     freopen("/Users/iantsai/cpp/input.txt","r",stdin);
  38.     freopen("/Users/iantsai/cpp/output.txt","w",stdout);
  39. }
  40. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  41. #else
  42. void setio(){}
  43. #define debug(x...)
  44. #endif
  45. #define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
  46. const int mxn = 6e5 + 5;
  47. vector<array<int,3>>adj[mxn], adj2[mxn];
  48. vector<int>g[mxn], rg[mxn];
  49. vector<array<int, 4>>op;
  50. vector<int>fix(mxn), ord;
  51. int scc[mxn], cnt = 0;
  52. bool vis[mxn];
  53. void rdfs(int v){
  54.     vis[v] = 1;
  55.     for(auto u : rg[v]){
  56.         if(vis[u]) continue;
  57.         rdfs(u);
  58.     }
  59.     ord.pb(v);
  60.     cout << v << '\n';
  61. }
  62. void dfs(int v, int c){
  63.     scc[v] = c;
  64.     for(auto u : g[v]){
  65.         if(scc[u]) continue;
  66.         dfs(u, c);
  67.     }
  68. }
  69. void init(int n){
  70.     ord.clear();
  71.     cnt = 0;
  72.     op.clear();
  73.     for(int i = 1; i <= 2 * n; i++){
  74.         scc[i] = 0;
  75.         rg[i].clear();
  76.         g[i].clear();
  77.         fix[i] = 0;
  78.         adj[i].clear();
  79.         adj2[i].clear();
  80.         vis[i] = 0;
  81.     }
  82. }
  83. void solve(){
  84.     int n, m;
  85.     n = 1;
  86.     g[1].pb(2);
  87.     rg[2].pb(1);
  88.     for(int i = 1; i <= 2 * n; i++){
  89.         if(!vis[i]) rdfs(i);
  90.     }
  91.     reverse(all(ord));
  92.     for(auto v : ord){
  93.         if(!scc[v]){
  94.             ++cnt;
  95.             dfs(v, cnt);
  96.         }
  97.         cout << v << ',' << scc[v] << ' '; 
  98.     }
  99. }
  100. signed main(){
  101.     TOI_is_so_de;
  102.     int t = 1;
  103.     cin >> t;
  104.     while(t--){
  105.         solve();
  106.     }
  107.     #ifdef local
  108.     CHECK();
  109.     #endif
  110. }
  111. /*
  112. input:
  113.  
  114. */
  115. #ifdef local
  116. void CHECK(){
  117.     cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
  118.     function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
  119.         std::ifstream file1(p1);
  120.         std::ifstream file2(p2);
  121.         if(!file1.is_open() || !file2.is_open()) return false;
  122.         std::string line1, line2;
  123.         while (getline(file1, line1) && getline(file2, line2)) {
  124.             if (line1 != line2)return false;
  125.         }
  126.         int cnta = 0, cntb = 0;
  127.         while(getline(file1,line1))cnta++;
  128.         while(getline(file2,line2))cntb++;
  129.         return cntb - cnta <= 1;
  130.     };
  131.     bool check = compareFiles("output.txt","expected.txt");
  132.     if(check) cerr<<"ACCEPTED\n";
  133.     else cerr<<"WRONG ANSWER!\n";
  134. }
  135. #else
  136. #endif
  137.  
  138.  
  139.  
  140.  
Success #stdin #stdout 0.02s 66132KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
2
2,1 1,2
https://ideone.com/HOzu36
language:
C++14 (gcc 8.3)
created:
38 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!