fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sd(x) scanf("%d", &(x))
  6. #define pii pair<int, int>
  7. #define F first
  8. #define S second
  9. #define all(c) ((c).begin()), ((c).end())
  10. #define sz(x) ((int)(x).size())
  11.  
  12. const int INF = 1 << 30;
  13.  
  14. void merge(vector<int> & a, vector<int> & b, int offset = 1){
  15.     if(b.empty()){
  16.         return;
  17.     }
  18.     if(a.empty()){
  19.         a = b;
  20.         return;
  21.     }
  22.     if(offset==1)assert(a.back() == b[0]);
  23.     copy(b.begin() + offset, b.end(), back_inserter(a));
  24. }
  25.  
  26. struct graph {
  27.   int n;
  28.   vector<vector<int>> adj, rdj, dist, prv;
  29.   graph(int n) : n(n), adj(n), rdj(n), dist(n), prv(n){ }
  30.   void add_edge(int src, int dst) {
  31.     adj[src].push_back(dst);
  32.     rdj[dst].push_back(src);
  33.   }
  34.  
  35.   vector<vector<int>> strongly_connected_components() { // kosaraju
  36.     vector<int> ord, visited(n);
  37.     vector<vector<int>> scc;
  38.     function<void(int,vector<vector<int>>&, vector<int>&)> dfs 
  39.       = [&](int u, vector<vector<int>> &adj, vector<int> &out) {
  40.       visited[u] = true;
  41.       for (int v: adj[u]) 
  42.         if (!visited[v]) dfs(v, adj, out);
  43.       out.push_back(u);
  44.     };
  45.     for (int u = 0; u < n; ++u)
  46.       if (!visited[u]) dfs(u, adj, ord);
  47.     fill(all(visited), false);
  48.     for (int i = n-1; i >= 0; --i) 
  49.       if (!visited[ord[i]]) 
  50.         scc.push_back({}), dfs(ord[i], rdj, scc.back()); 
  51.     return scc;
  52.   }
  53.  
  54.     void bfs(int s){
  55.         dist[s].assign(n, INF);
  56.         prv[s].assign(n, -1);
  57.         dist[s][s] = 0;
  58.         queue<int> q; q.push(s);
  59.         while(!q.empty()){
  60.             int u = q.front();
  61.             q.pop();
  62.             for(int v : adj[u]) if(dist[s][v] == INF){
  63.                 dist[s][v] = dist[s][u] + 1;
  64.                 prv[s][v] = u;
  65.                 q.push(v);
  66.             }
  67.         }
  68.     }
  69.  
  70.     vector<int> getPath(int a, int b){
  71.         int curr = b;
  72.         vector<int> ret;
  73.         while(curr != a){
  74.             ret.push_back(curr);
  75.             curr = prv[a][curr];
  76.         }
  77.         ret.push_back(a);
  78.         reverse(all(ret));
  79.         return ret;
  80.     }
  81.  
  82.     void precompute(){
  83.         for(int i= 0; i < n; i++)bfs(i);
  84.     }
  85.  
  86.     vector<int> go_scc(vector<int> nodes, int st, int en){
  87.         if(sz(nodes) == 1){
  88.             return nodes;
  89.         }
  90.         int a = -1, b = -1, mx = -1;
  91.         for(int i : nodes) for(int j : nodes) if(dist[i][j] > mx || (dist[i][j] == mx && i == st)){
  92.             mx = dist[i][j];
  93.             a = i, b = j;
  94.         }
  95.         vector<int> walk = getPath(a, b);
  96.         set<int> vis;
  97.         for(int it : walk) vis.insert(it);
  98.         for(int i : nodes) if(!vis.count(i)){
  99.             vector<int> now = getPath(walk.back(), i);
  100.             merge(walk, now);
  101.         }
  102.         b = walk.back();
  103.         if( (st == -1 || st == a) && (en == -1 || en == b)) return walk;
  104.         vector<int> lft, rgt;
  105.         if(en != -1 && dist[b][en] == mx){
  106.             vector<int> rev_walk = getPath(b, en);
  107.             reverse(all(rev_walk));
  108.             vis.clear();
  109.             for(auto it : rev_walk) vis.insert(it);
  110.             for(int i : nodes) if(!vis.count(i)){
  111.                 vector<int> now = getPath(i, rev_walk.back());
  112.                 reverse(all(now));
  113.                 merge(rev_walk, now);
  114.             }
  115.             if(st != -1){
  116.                 vector<int> now = getPath(st, rev_walk.back());
  117.                 reverse(all(now));
  118.                 merge(rev_walk, now);
  119.             }
  120.             reverse(all(rev_walk));
  121.             return rev_walk;
  122.         } else{
  123.             if(st != -1) lft = getPath(st, walk[0]);
  124.             if(en != -1) rgt = getPath(walk.back(), en);
  125.             merge(lft, walk);
  126.             merge(lft, rgt);
  127.             return lft; 
  128.         }
  129.     }
  130.     vector<int> getWalk(){
  131.         precompute();
  132.         vector<vector<int>> scc = strongly_connected_components();
  133.         vector<int> where(n, -1);
  134.         for(int i = 0; i < sz(scc); i++) for(int j : scc[i]) where[j] = i;
  135.         vector<pii> edge(n, {-1, -1});
  136.         for(int i = 0; i < n; i++) for(int j : adj[i]){
  137.             if(where[j] == where[i] + 1) edge[where[i]] = {i, j};
  138.         }
  139.         for(int i = 0; i + 1 < sz(scc); i++) if(edge[i].F == -1) return {};
  140.         vector<int> walk;
  141.         for(int i = 0; i < sz(scc); i++){
  142.             int st = i == 0 ? -1 : edge[i - 1].S;
  143.             int en = i == sz(scc) - 1 ? -1 : edge[i].F;
  144.             vector<int> now = go_scc(scc[i], st, en);
  145.             merge(walk, now, 0);
  146.         }
  147.         return walk;
  148.     }
  149. };
  150.  
  151. int main(){
  152.     int t; sd(t);
  153.     while(t--){
  154.         int n, m;
  155.         sd(n); sd(m);
  156.         graph g(n);
  157.         for(int i = 0; i < m; i++){
  158.             int u, v; sd(u); sd(v); u--; v--;
  159.             g.add_edge(u, v);
  160.         }
  161.  
  162.         vector<int> walk = g.getWalk();
  163.         if(walk.empty()){
  164.             printf("-1\n");
  165.             continue;
  166.         }
  167.         printf("%d ", sz(walk) - 1);
  168.         for(auto it : walk) printf("%d ", it + 1);
  169.         printf("\n");
  170.     }
  171. }
Runtime error #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EKG5rS
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!