#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
template<bool Enable_small_to_large = true>
struct disjoint_set{
int n, _classes;
vector<int> p;
disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
int make_set(){
p.push_back(-1);
++ _classes;
return n ++;
}
int classes() const{
return _classes;
}
int root(int u){
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b){
return root(a) == root(b);
}
int size(int u){
return -p[root(u)];
}
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
bool merge(int u, int v, auto act){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
bool swapped = false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
p[u] += p[v], p[v] = u;
act(u, v, swapped);
return true;
}
void clear(){
_classes = n;
fill(p.begin(), p.end(), -1);
}
vector<vector<int>> group_up(){
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
};
const int N = 3e3 + 5;
int subtask;
int n;
int a[N][N];
disjoint_set dsu(N);
vi adj[N];
int col[N], cntcol;
int used[N];
int dfs_find_color(int u, int p, int orig, int cnt){
if (~p){
used[col[u]]++;
if (used[col[u]] == 1){
if (a[orig][u] == cnt){
return col[u];
}
cnt++;
}
}
Fora(v, adj[u]){
if (v == p or col[v] == 0){
continue;
}
int ans = dfs_find_color(v, u, orig, cnt);
if (ans != 0){
return ans;
}
}
used[col[u]]--;
return 0;
}
void dfs_color(int u, int p){
if (~p){
fill(used + 1, used + n + 1, 0);
int ans = dfs_find_color(u, -1, u, 1);
if (ans == 0){
col[u] = ++cntcol;
}
else{
col[u] = ans;
}
}
Fora(v, adj[u]){
if (v == p){
continue;
}
dfs_color(v, u);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> subtask;
cin >> n;
For(u, 0, n){
For(v, 0, n){
cin >> a[u][v];
}
}
For(u, 0, n){
For(v, 0, n){
if (a[u][v] == 1){
dsu.merge(u, v, [&](int _u, int _v, bool _sw){
adj[u].emplace_back(v);
adj[v].emplace_back(u);
});
}
}
}
For(u, 0, n){
For(v, 0, n){
if (a[u][v] == 2){
dsu.merge(u, v, [&](int _u, int _v, bool _sw){
adj[u].emplace_back(v);
adj[v].emplace_back(u);
});
}
}
}
col[0] = 1;
cntcol = 1;
dfs_color(0, -1);
For(u, 0, n){
cout << col[u] << ' ';
} cout << endl;
For(u, 0, n){
Fora(v, adj[u]){
if (u < v){
cout << u + 1 << ' ' << v + 1 << endl;
}
}
}
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
izlet.cpp:51:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
51 | bool merge(int u, int v, auto act){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
459 ms |
53408 KB |
Output is correct |
| 3 |
Correct |
464 ms |
53444 KB |
Output is correct |
| 4 |
Correct |
476 ms |
53280 KB |
Output is correct |
| 5 |
Correct |
471 ms |
53200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
448 ms |
35900 KB |
Output is correct |
| 2 |
Correct |
476 ms |
53364 KB |
Output is correct |
| 3 |
Correct |
623 ms |
74040 KB |
Output is correct |
| 4 |
Correct |
655 ms |
74816 KB |
Output is correct |
| 5 |
Correct |
441 ms |
53340 KB |
Output is correct |
| 6 |
Correct |
493 ms |
60384 KB |
Output is correct |
| 7 |
Correct |
367 ms |
49316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
459 ms |
53408 KB |
Output is correct |
| 3 |
Correct |
464 ms |
53444 KB |
Output is correct |
| 4 |
Correct |
476 ms |
53280 KB |
Output is correct |
| 5 |
Correct |
471 ms |
53200 KB |
Output is correct |
| 6 |
Correct |
448 ms |
35900 KB |
Output is correct |
| 7 |
Correct |
476 ms |
53364 KB |
Output is correct |
| 8 |
Correct |
623 ms |
74040 KB |
Output is correct |
| 9 |
Correct |
655 ms |
74816 KB |
Output is correct |
| 10 |
Correct |
441 ms |
53340 KB |
Output is correct |
| 11 |
Correct |
493 ms |
60384 KB |
Output is correct |
| 12 |
Correct |
367 ms |
49316 KB |
Output is correct |
| 13 |
Correct |
479 ms |
54396 KB |
Output is correct |
| 14 |
Correct |
609 ms |
61396 KB |
Output is correct |
| 15 |
Correct |
473 ms |
53340 KB |
Output is correct |
| 16 |
Correct |
536 ms |
57912 KB |
Output is correct |
| 17 |
Correct |
521 ms |
59768 KB |
Output is correct |
| 18 |
Correct |
464 ms |
53424 KB |
Output is correct |
| 19 |
Correct |
506 ms |
53328 KB |
Output is correct |
| 20 |
Correct |
473 ms |
53480 KB |
Output is correct |
| 21 |
Correct |
488 ms |
54220 KB |
Output is correct |
| 22 |
Correct |
506 ms |
53628 KB |
Output is correct |
| 23 |
Correct |
478 ms |
54220 KB |
Output is correct |
| 24 |
Correct |
533 ms |
60516 KB |
Output is correct |
| 25 |
Correct |
467 ms |
53688 KB |
Output is correct |
