fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define all(v) v.begin(), v.end()
  6.  
  7. const ll INF = 4e18;
  8.  
  9. void fileio() {
  10. #ifndef ONLINE_JUDGE
  11.     freopen("input.txt", "r", stdin);
  12.     freopen("output.txt", "w", stdout);
  13. #endif
  14. }
  15.  
  16. int n, m;
  17. vector<vector<int>> adj;
  18. vector<int> vis;
  19. int dx[]={-1 ,1 ,0 , 0};
  20. int dy[]={0 , 0 ,-1 ,1};
  21. /* =========================
  22.    DFS
  23.    ========================= */
  24.  
  25. void dfs(int u) {
  26.     vis[u] = 1;
  27.  
  28.     for (int v : adj[u]) {
  29.         if (!vis[v]) {
  30.             dfs(v);
  31.         }
  32.     }
  33. }
  34.  
  35. /* =========================
  36.    BFS
  37.    Shortest path in unweighted graph
  38.    ========================= */
  39.  
  40. vector<int> bfs(int src) {
  41.     vector<int> dist(n + 1, -1);
  42.     queue<int> q;
  43.  
  44.     dist[src] = 0;
  45.     q.push(src);
  46.  
  47.     while (!q.empty()) {
  48.         int u = q.front();
  49.         q.pop();
  50.  
  51.         for (int v : adj[u]) {
  52.             if (dist[v] == -1) {
  53.                 dist[v] = dist[u] + 1;
  54.                 q.push(v);
  55.             }
  56.         }
  57.     }
  58.  
  59.     return dist;
  60. }
  61.  
  62. /* =========================
  63.    Connected Components
  64.    Undirected graph
  65.    ========================= */
  66.  
  67. int count_components() {
  68.     vis.assign(n + 1, 0);
  69.  
  70.     int components = 0;
  71.  
  72.     for (int i = 1; i <= n; i++) {
  73.         if (!vis[i]) {
  74.             components++;
  75.             dfs(i);
  76.         }
  77.     }
  78.  
  79.     return components;
  80. }
  81.  
  82. /* =========================
  83.    Cycle Detection
  84.    Undirected graph
  85.    ========================= */
  86.  
  87. bool dfs_cycle_undirected(int u, int parent) {
  88.     vis[u] = 1;
  89.  
  90.     for (int v : adj[u]) {
  91.         if (!vis[v]) {
  92.             if (dfs_cycle_undirected(v, u)) {
  93.                 return true;
  94.             }
  95.         } else if (v != parent) {
  96.             return true;
  97.         }
  98.     }
  99.  
  100.     return false;
  101. }
  102.  
  103. bool has_cycle_undirected() {
  104.     vis.assign(n + 1, 0);
  105.  
  106.     for (int i = 1; i <= n; i++) {
  107.         if (!vis[i]) {
  108.             if (dfs_cycle_undirected(i, -1)) {
  109.                 return true;
  110.             }
  111.         }
  112.     }
  113.  
  114.     return false;
  115. }
  116.  
  117. /* =========================
  118.    Cycle Detection
  119.    Directed graph
  120.    0 = unvisited
  121.    1 = currently visiting
  122.    2 = finished
  123.    ========================= */
  124.  
  125. vector<int> color;
  126.  
  127. bool dfs_cycle_directed(int u) {
  128.     color[u] = 1;
  129.  
  130.     for (int v : adj[u]) {
  131.         if (color[v] == 0) {
  132.             if (dfs_cycle_directed(v)) {
  133.                 return true;
  134.             }
  135.         } else if (color[v] == 1) {
  136.             return true;
  137.         }
  138.     }
  139.  
  140.     color[u] = 2;
  141.     return false;
  142. }
  143.  
  144. bool has_cycle_directed() {
  145.     color.assign(n + 1, 0);
  146.  
  147.     for (int i = 1; i <= n; i++) {
  148.         if (color[i] == 0) {
  149.             if (dfs_cycle_directed(i)) {
  150.                 return true;
  151.             }
  152.         }
  153.     }
  154.  
  155.     return false;
  156. }
  157.  
  158. /* =========================
  159.    Topological Sort DFS
  160.    Directed Acyclic Graph only
  161.    Not lexicographically smallest
  162.    ========================= */
  163.  
  164. vector<int> topo;
  165. bool cycle;
  166.  
  167. void dfs_topo(int u) {
  168.     color[u] = 1;
  169.  
  170.     for (int v : adj[u]) {
  171.         if (color[v] == 0) {
  172.             dfs_topo(v);
  173.         } else if (color[v] == 1) {
  174.             cycle = true;
  175.         }
  176.     }
  177.  
  178.     color[u] = 2;
  179.     topo.push_back(u);
  180. }
  181.  
  182. vector<int> topo_sort_dfs() {
  183.     color.assign(n + 1, 0);
  184.     topo.clear();
  185.     cycle = false;
  186.  
  187.     for (int i = 1; i <= n; i++) {
  188.         if (color[i] == 0) {
  189.             dfs_topo(i);
  190.         }
  191.     }
  192.  
  193.     if (cycle) {
  194.         return {};
  195.     }
  196.  
  197.     reverse(all(topo));
  198.     return topo;
  199. }
  200.  
  201. /* =========================
  202.    Topological Sort Kahn
  203.    Lexicographically smallest
  204.    Use this for SPOJ TOPOSORT
  205.    ========================= */
  206.  
  207. vector<int> topo_sort_kahn_lexicographical() {
  208.     vector<int> indeg(n + 1, 0);
  209.  
  210.     for (int u = 1; u <= n; u++) {
  211.         for (int v : adj[u]) {
  212.             indeg[v]++;
  213.         }
  214.     }
  215.  
  216.     priority_queue<int, vector<int>, greater<int>> pq;
  217.  
  218.     for (int i = 1; i <= n; i++) {
  219.         if (indeg[i] == 0) {
  220.             pq.push(i);
  221.         }
  222.     }
  223.  
  224.     vector<int> ans;
  225.  
  226.     while (!pq.empty()) {
  227.         int u = pq.top();
  228.         pq.pop();
  229.  
  230.         ans.push_back(u);
  231.  
  232.         for (int v : adj[u]) {
  233.             indeg[v]--;
  234.  
  235.             if (indeg[v] == 0) {
  236.                 pq.push(v);
  237.             }
  238.         }
  239.     }
  240.  
  241.     if ((int)ans.size() != n) {
  242.         return {};
  243.     }
  244.  
  245.     return ans;
  246. }
  247.  
  248. /* =========================
  249.    Bipartite Check
  250.    Undirected graph
  251.    ========================= */
  252.  
  253. bool is_bipartite() {
  254.     vector<int> color_bip(n + 1, -1);
  255.  
  256.     for (int start = 1; start <= n; start++) {
  257.         if (color_bip[start] != -1) continue;
  258.  
  259.         queue<int> q;
  260.         q.push(start);
  261.         color_bip[start] = 0;
  262.  
  263.         while (!q.empty()) {
  264.             int u = q.front();
  265.             q.pop();
  266.  
  267.             for (int v : adj[u]) {
  268.                 if (color_bip[v] == -1) {
  269.                     color_bip[v] = color_bip[u] ^ 1;
  270.                     q.push(v);
  271.                 } else if (color_bip[v] == color_bip[u]) {
  272.                     return false;
  273.                 }
  274.             }
  275.         }
  276.     }
  277.  
  278.     return true;
  279. }
  280.  
  281. /* =========================
  282.    Dijkstra
  283.    Weighted graph
  284.    No negative weights
  285.    ========================= */
  286.  
  287. vector<vector<pair<int, ll>>> wadj;
  288.  
  289. vector<ll> dijkstra(int src) {
  290.     vector<ll> dist(n + 1, INF);
  291.  
  292.     priority_queue<
  293.         pair<ll, int>,
  294.         vector<pair<ll, int>>,
  295.         greater<pair<ll, int>>
  296.     > pq;
  297.  
  298.     dist[src] = 0;
  299.     pq.push({0, src});
  300.  
  301.     while (!pq.empty()) {
  302.         auto [d, u] = pq.top();
  303.         pq.pop();
  304.  
  305.         if (d != dist[u]) continue;
  306.  
  307.         for (auto [v, w] : wadj[u]) {
  308.             if (dist[u] + w < dist[v]) {
  309.                 dist[v] = dist[u] + w;
  310.                 pq.push({dist[v], v});
  311.             }
  312.         }
  313.     }
  314.  
  315.     return dist;
  316. }
  317.  
  318. /* =========================
  319.    Main solve
  320.    ========================= */
  321.  
  322. void solve() {
  323.     cin >> n >> m;
  324.  
  325.     adj.assign(n + 1, vector<int>());
  326.     vis.assign(n + 1, 0);
  327.  
  328.     for (int i = 0; i < m; i++) {
  329.         int u, v;
  330.         cin >> u >> v;
  331.  
  332.         // Undirected:
  333.         // adj[u].push_back(v);
  334.         // adj[v].push_back(u);
  335.  
  336.         // Directed:
  337.         adj[u].push_back(v);
  338.     }
  339.  
  340.     vector<int> ans = topo_sort_kahn_lexicographical();
  341.  
  342.     if (ans.empty()) {
  343.         cout << "Sandro fails.\n";
  344.         return;
  345.     }
  346.  
  347.     for (int x : ans) {
  348.         cout << x << " ";
  349.     }
  350.  
  351.     cout << '\n';
  352. }
  353.  
  354. int main() {
  355.     ios::sync_with_stdio(false);
  356.     cin.tie(nullptr);
  357.  
  358.     //fileio();
  359.  
  360.     int t = 1;
  361.     // cin >> t;
  362.  
  363.     while (t--) {
  364.         solve();
  365.     }
  366.  
  367.     return 0;
  368. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sandro fails.
https://ideone.com/ylMZth
language:
C++ (gcc 8.3)
created:
1 hour 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!