이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const ll N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const ll maxk = 1e6;
int f[3000][3000], n, cl[3000], p[3000], sz[3000], cnt[3000];
vector<int> g[3000];
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
void unite(int a, int b) {
if (find(a) == find(b)) return;
g[a].push_back(b), g[b].push_back(a);
a = find(a), b = find(b);
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
void check_dfs(int x, int p, int root) {
if (p != -1 && f[root][x] == f[root][p] && !cnt[cl[x]]) {
cl[root] = cl[x];
}
if (p != -1) ++cnt[cl[x]];
for (auto to : g[x]) {
if (cl[to] && to != p) {
check_dfs(to, x, root);
}
}
if (p != -1) --cnt[cl[x]];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> n;
for (int i = 0; i < n; i++) {
p[i] = i, sz[i] = 1;
for (int j = 0; j < n; j++)
cin >> f[i][j];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (f[i][j] == 1) {
unite(i, j);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (f[i][j] == 2) {
unite(i, j);
}
}
}
queue<int> q;
q.push(0);
int ptr = 0;
while(!q.empty()) {
int x = q.front();
q.pop();
if (cl[x]) continue;
check_dfs(x, -1, x);
if (!cl[x]) cl[x] = ++ptr;
for (auto to : g[x]) {
if (!cl[to]) q.push(to);
}
}
for (int i = 0; i < n; i++) {
cout << cl[i] << ' ';
}
cout << endl;
for (int i = 0; i < n; i++) {
for (auto to : g[i]) {
if (to < i) continue;
cout << i + 1 << ' ' << to + 1 << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |