Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fi first
- #define se second
- #define pb push_back
- vector <int> v[100010];
- vector <pair<int, int> > pos[100010];
- int us[100010];
- bool cmp(pair<int, int> a, pair<int, int> b) {
- if(a.fi == 0)
- return 1;
- if(b.fi == 0)
- return 0;
- return a.fi < b.fi;
- }
- bool dfs(int cur, int g = 1, int l = 0) {
- us[cur] = g;
- int d = 0;
- for(auto x: v[cur]) {
- // cout << cur << ' ' << x << "\n";
- // cout << us[cur] << ' ' << g << '\n';
- // cout << us[x] << ' ' << g % 2 + 1 << "\n\n";
- if(us[x] && us[x] != g % 2 + 1) {
- cout << "-1";
- exit(0);
- } if(!us[x]) {
- d = 1;
- int q = (l >= 0 ? 1: -1);
- if(dfs(x, g % 2 + 1, q)) {
- if(l == 100) {
- cout << "-1";
- exit(0);
- } else if(l == -1) {
- pos[cur].pb({-1, x});
- l = 100;
- } else {
- pos[cur].pb({1, x});
- l = (l == 0 ? -1: 100);
- }
- } else {
- pos[cur].pb({0, x});
- }
- }
- }
- sort(pos[cur].begin(), pos[cur].end());
- return d;
- }
- vector <pair<int, int> > l[2];
- int mn[2];
- void dfs1(int cur, int line = 0) {
- // cout << cur << ' ' << line << "\n";
- for(auto x: pos[cur]) {
- // cout << x.fi << ' ' << x.se << '\n';
- if(x.fi == -1) {
- dfs1(x.se, line^1);
- // l[line^1].pb({mn[line^1], x.se});
- mn[line^1]++;
- } else if(x.fi == 0) {
- l[line^1].pb({mn[line^1], x.se});
- mn[line^1]++;
- }
- }
- // cout << "\n";
- l[line].pb({mn[line], cur});
- if(!pos[cur].empty() && pos[cur].back().fi == 1) {
- // l[line^1].pb({mn[line^1], pos[cur].back().se});
- mn[line^1]++;
- dfs1(pos[cur].back().se, line^1);
- }
- }
- int main() {
- // freopen("input.txt", "r", stdin);
- freopen("gods.in", "r", stdin);
- freopen("gods.out", "w", stdout);
- int n, i, x, j, y;
- cin >> n;
- for(i = 1; i <= n; i++) {
- cin >> x;
- for(j = 1; j <= x; j++) {
- cin >> y;
- v[i].pb(y);
- }
- }
- for(i = 1; i <= n; i++) {
- if(!us[i]) {
- if(v[i].size() == 1)
- dfs(v[i][0]), dfs1(v[i][0]);
- else
- dfs(i), dfs1(i);
- }
- }
- cout << l[0].size() << ' ' << l[1].size() << "\n";
- for(auto x: l[0])
- cout << x.se << " ";
- cout << "\n";
- for(auto x: l[1])
- cout << x.se << " ";
- cout << "\n";
- ////
- }
Advertisement
Add Comment
Please, Sign In to add comment