fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define en "\n"
  4. #define matrix vector<vector<int>>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define elif else if
  9. using namespace std;
  10.  
  11. const int MAXN = 1e5 + 5, INF = INT_MAX, MOD = 1e9 + 7;
  12. ll n, t = 1, m, cnt, sccid;
  13. vector<ll> a(MAXN), scc(MAXN), num(MAXN), low(MAXN), out_deg(MAXN);
  14. matrix adj;
  15. stack<int> st;
  16.  
  17. void dfs(int u){
  18.     low[u] = num[u] = ++cnt;
  19.     st.push(u);
  20.     for (int v : adj[u]){
  21.         if (!scc[v]){
  22.             if (num[v] == 0){
  23.                 dfs(v);
  24.                 low[u] = min(low[u], low[v]);
  25.             }
  26.             else low[u] = min(low[u], num[v]);
  27.         }
  28.     }
  29.     if (num[u] == low[u]){
  30.         ++sccid;
  31.         while (1){
  32.             int v = st.top();
  33.             st.pop();
  34.             scc[v] = sccid;
  35.             if (v == u) break;
  36.         }
  37.     }
  38. }
  39.  
  40. void input(){
  41.     cin >> n >> m;
  42.     adj.assign(n + 1, {});
  43.     while (m--){
  44.         int u, v;
  45.         cin >> u >> v;
  46.         adj[u].pb(v);
  47.     }
  48. }
  49.  
  50. void solve(){
  51.     for (int i = 1; i <= n; i++)
  52.         if (!num[i]) dfs(i);
  53.     vector<int> out_scc(sccid + 1, 0); 
  54.     for (int u = 1; u <= n; u++){
  55.         for (int v : adj[u]){
  56.             if (scc[u] != scc[v]){
  57.                 out_scc[scc[u]]++;
  58.             }
  59.         }
  60.     }
  61.     int cnt_zero = 0;
  62.     int target_scc = -1;
  63.     for (int i = 1; i <= sccid; i++){
  64.         if (out_scc[i] == 0){
  65.             cnt_zero++;
  66.             target_scc = i;
  67.         }
  68.     }
  69.     if (cnt_zero != 1){
  70.         cout << 0;
  71.     } else {
  72.         vector<int> res;
  73.         for (int i = 1; i <= n; i++){
  74.             if (scc[i] == target_scc) res.pb(i);
  75.         }
  76.         cout << res.size() << en;
  77.         for (int x : res) cout << x << " ";
  78.     }
  79. }
  80.  
  81. int main(){
  82.     //freopen("input.inp", "r", stdin);
  83.     //freopen("input.out", "w", stdout);
  84.  
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(nullptr); cout.tie(nullptr);
  87.  
  88.     //cin >> t;
  89.     while (t--){
  90.         input();
  91.         solve();
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 7020KB
comments (?)
stdin
copy 
4 4
1 2
3 2
4 3
2 1
stdout
copy 
2
1 2
https://ideone.com/JwdcH7
problem CAPCITY, based on SPOJ submission 35539551 (CPP14), 2026-02-16 04:44:22
language:
C++14 (gcc 8.3)
created:
1 day 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!