fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m, d[100000];
  5. vector<int> a[100000], g[100000], was(100000, 0), q, lo(100000, -100000), ans;
  6.  
  7. void dfs(int v, int p) {
  8. 	was[v] = 1;
  9. 	for(int to : g[v])
  10. 		if(to != p)
  11. 			if(was[to] == 1) { cout << "No"; exit(0); }
  12. 			else if(was[to] == 0) dfs(to, v);
  13. }
  14.  
  15. int main() {
  16. 	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  17. 	cin >> n >> m;
  18. 	for(int i = 0; i < n; i++) {
  19. 		int l; cin >> l; a[i].resize(l);
  20. 		for(int j = 0; j < l; j++) cin >> a[i][j], a[i][j]--;
  21. 		if(i) {
  22. 			int l0 = a[i - 1].size(), p = -1;
  23. 			for(int j = 0; j < min(l0, l); j++)
  24. 				if(a[i - 1][j] != a[i][j]) {
  25. 					p = j; break;
  26. 				}
  27. 			if(p == -1 && l0 > l) return cout << "No", 0;
  28. 			if(p != -1) g[a[i - 1][p]].push_back(a[i][p]), d[a[i][p]]++;
  29. 		}
  30. 	}
  31. 	dfs(0, -1);
  32. 	for(int i = 0; i < m; i++) if(!d[i]) q.push_back(i);
  33. 	while(!q.empty()) {
  34. 		int v = q.back();
  35. 		q.pop_back();
  36. 		if(lo[v] > v) return cout << "No", 0;
  37. 		int z = v;
  38. 		if(v - 100000 >= lo[v]) {
  39. 			ans.push_back(v);
  40. 			z -= 100000;
  41. 		}
  42. 		for(int to : g[v]) {
  43. 			lo[to] = max(lo[to], z);
  44. 			if(--d[to] == 0)
  45. 				q.push_back(to);
  46. 		}
  47. 	}
  48. 	cout << "Yes\n" << ans.size() << '\n';
  49. 	for(int y : ans) cout << y + 1 << ' ';
  50. }
Success #stdin #stdout 0s 21144KB
comments (?)
stdin
copy 
4 3
4 3 2 2 1
3 1 1 3
3 2 3 3
2 3 1
stdout
copy 
No
https://ideone.com/GHO3Kn
language:
C++14 (gcc 8.3)
created:
6 years 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!