fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #define all(x) x.begin(),x.end()
  5. const int N = 1e6 + 5;
  6. int n, m;
  7. vector<int> adj[N], adj2[N];
  8. int low[N], num[N], visited[N], dd, need[1 << 16];
  9. int cnt, deg[N], mmb;
  10. stack<int> st;
  11. void dfs(int u){
  12.     st.push(u);
  13.     num[u] = low[u] = ++cnt;
  14.     for(auto x : adj2[u]){
  15.         if(num[x]) low[u] = min(low[u], num[x]);
  16.         else {
  17.             dfs(x);
  18.             low[u] = min(low[u], low[x]);
  19.         }
  20.     }
  21.     if(low[u] == num[u]){
  22.         int d = 0;
  23.         mmb++;
  24.         while(1){
  25.             int x = st.top(); st.pop();
  26.             d++;
  27.             num[x] = low[x] = n + 1;
  28.             if(x == u) break;
  29.         }
  30.     }
  31. }
  32. vector<int> valid;
  33. void init(int p, int val, int cnt) {
  34.     if(cnt > m) return;
  35.     if(p == n) {
  36.         valid.push_back(val);
  37.         int res = 0;
  38.         for(int i = 1; i <= n; i++)
  39.             if((val >> (i - 1)) & 1)
  40.                 for(int x : adj[i])
  41.                     res |= (1 << (x - 1));
  42.         need[val] = res;
  43.         return;
  44.     }
  45.     init(p + 1, val | (1 << p), cnt + 1);
  46.     init(p + 1, val, cnt);
  47. }
  48.  
  49. int bitmask(){
  50.     int dp[1 << 16], cntt[1 << 16];
  51.     fill(dp, dp + (1 << n), 1e9);
  52.     dp[0] = 0;
  53.     for (int mask = 0; mask < (1 << n); ++mask) {
  54.         cntt[mask] = __builtin_popcount(mask);
  55.     }
  56.     for (int mask = 0; mask < (1 << n); ++mask) {
  57.         int T = 0;
  58.         for (int i = 1; i <= n; ++i) {
  59.             if (!(mask & (1 << (i - 1))) && (need[1 << (i - 1)] & mask) == need[1 << (i - 1)]) {
  60.                 T |= (1 << (i - 1));
  61.             }
  62.         }
  63.         for (int submask = T; submask > 0; submask = (submask - 1) & T) {
  64.             if (cntt[submask] > m) continue;
  65.             dp[mask | submask] = min(dp[mask | submask], dp[mask] + 1);
  66.         }
  67.     }
  68.     return dp[(1 << n) - 1];
  69. }
  70.  
  71.  
  72. int topo(){
  73.     int dp[N];
  74.     queue<int> q;
  75.     for(int i = 1; i <= n; i++)
  76.         if(!deg[i]) q.push(i);
  77.     while(q.size())  {
  78.         int u = q.front();
  79.         q.pop();
  80.         for(auto v : adj2[u]) {
  81.             deg[v]--;
  82.             dp[v] = max(dp[v], dp[u] + 1);
  83.             if(!deg[v]) q.push(v);
  84.         }
  85.     }
  86.     int ans = 0;
  87.     for(int i = 1; i <= n; i++)
  88.         ans = max(ans, dp[i] + 1);
  89.     return ans;
  90. }
  91.  
  92. int main(){
  93.     if(fopen("vd.inp", "r")){
  94.         freopen("vd.inp", "r", stdin);
  95.         freopen("vd.out", "w", stdout);
  96.     }
  97.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  98.     cin >> n >> m;
  99.     for(int i = 1; i <= n; i++){
  100.         int k; cin >> k;
  101.         for(int j = 1; j <= k; j++){
  102.             int x; cin >> x;
  103.             adj[i].push_back(x);
  104.             adj2[x].push_back(i);
  105.             deg[i]++;
  106.             if(x == i) {
  107.                 cout << -1;
  108.                 return 0;
  109.             }
  110.         }
  111.     }
  112.     for(int i = 1; i <= n; i++) if(!num[i]) dfs(i);
  113.     if(mmb != n) {
  114.         cout << -1;
  115.         return 0;
  116.     }
  117.     if(m >= n) cout << topo();
  118.     else {
  119.         init(0, 0, 0);
  120.         //sort(all(valid));
  121.         //valid.erase(unique(all(valid)), valid.end());
  122.         cout << bitmask();
  123.     }
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.01s 50704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bTFEo8
language:
C++14 (clang 8.0)
created:
17 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!