boj2026/7777.cpp at main · joonghak/boj2026 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
using namespace std;

typedef long long ll;
const long long INF = 1e9 + 7;

// reference : https://github.com/justiceHui/icpc-teamnote
vector<int> DominatorTree(const vector<vector<int>>& g, int src) { // 0-based
	const int n = g.size();
	vector<vector<int>> rg(n), buf(n);
	vector<int> r(n), val(n), idom(n, -1), sdom(n, -1), par(n), u(n), o;
	iota(r.begin(), r.end(), 0), iota(val.begin(), val.end(), 0);
	for (int i = 0; i < n; i++) for (auto j : g[i]) rg[j].push_back(i);
	auto Find = [&](int v, auto&& Find) -> int {
		if (v == r[v]) return v;
		int ret = Find(r[v], Find);
		if (sdom[val[v]] > sdom[val[r[v]]]) val[v] = val[r[v]];
		return r[v] = ret;
	};
	auto DFS = [&](int v, auto&& DFS) -> void {
		sdom[v] = o.size(); o.push_back(v);
		for (auto i : g[v]) if (sdom[i] == -1) par[i] = v, DFS(i, DFS);
	};
	DFS(src, DFS), reverse(o.begin(), o.end());
	for (auto& i : o) {
		if (sdom[i] == -1) continue;
		for (auto j : rg[i]) {
			if (sdom[j] == -1) continue;
			int x = val[Find(j, Find), j];
			if (sdom[i] > sdom[x]) sdom[i] = sdom[x];
		}
		buf[o[o.size() - sdom[i] - 1]].push_back(i);
		for (auto j : buf[par[i]]) u[j] = val[Find(j, Find), j];
		buf[par[i]].clear();
		r[i] = par[i];
	}
	idom[src] = src, reverse(o.begin(), o.end());
	for (auto i : o) { // WARNING : if different, takes idom
		if (i != src) idom[i] = sdom[i] == sdom[u[i]] ? sdom[i] : idom[u[i]];
	}
	for (auto i : o) if (i != src) idom[i] = o[idom[i]];
	return idom; // unreachable -> ret[i] = -1
}

int n,k;

int main() {
    fastio;
    cin >> n >> k; //[0,k)
    n++;
    vector<vector<int>> g(n);
    for(int i=k;i<n-1;i++){
        g[n-1].push_back(i);
    }
    for(int i=0;i<k;i++){
        int t;
        cin >> t;
        for(int j=0;j<t;j++){
            int a;
            cin >> a;
            g[a-1].push_back(i);
        }
    }
    auto v=DominatorTree(g, n-1);
    for(int i=0;i<k;i++){
        if(v[i]==-1) continue;
        while(v[v[i]] != n-1) v[i]=v[v[i]];
    }
    vector<int> aans;
    vector<pair<int,int>> ans;
    for(int i=0;i<k;i++){
        if(v[i]==-1){
            aans.push_back(i);
            continue;
        }
        for(int j=i+1;j<n-1;j++){
            if(v[j]==-1) continue;
            if((v[i]!=n-1 && (v[i]==v[j] || v[i]==j)) || v[j]==i) ans.push_back({i, j});
        }
    }
    cout << aans.size() << "\n";
    for(auto i: aans){
        cout << i+1<<" ";
    }
    cout << "\n";
    cout << ans.size()<<"\n";
    for(auto[a,b]:ans){
        cout << a+1 <<" "<< b+1<<"\n";
    }


    return 0;
}