#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using pii = pair<int, int>;
const int MX = 3e3 + 5;
int pr[MX];
int gp(int n) { return pr[n]?(pr[n]=gp(pr[n])):n; }
void un(int x, int y) {
x=gp(x), y=gp(y);
if (x!=y) pr[y]=x;
}
int T, N, mt[MX][MX], clr[MX], dst[MX][MX];
vector<int> stk;
vector<pii> a;
void dfs(int n, int p) {
if (p) {
pii mn(MX, 0);
for (auto &i:stk) if (mt[i][n]==mt[i][p]) mn=min(mn, pii(dst[i][n], clr[i]));
if (mn.second) clr[n]=mn.second;
else clr[n]=++T;
}else clr[n]=++T;
stk.eb(n);
for (int i=1; i<=N; i++) if (!clr[i]&&gp(i)==i&&mt[i][n]==2) {
for (auto &j:stk) dst[i][j]=dst[j][i]=dst[n][j]+1;
a.eb(n, i);
dfs(i, n);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>T>>N;
for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) {
cin>>mt[i][j];
if (mt[i][j]==1) un(i, j);
}
dfs(gp(1), T=0);
for (int i=1; i<=N; i++) cout<<clr[gp(i)]<<' ';
cout<<'\n';
for (auto &i:a) cout<<i.first<<' '<<i.second<<'\n';
for (int i=1; i<=N; i++) if (gp(i)!=i) cout<<gp(i)<<' '<<i<<'\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
713 ms |
71988 KB |
Output is correct |
| 3 |
Correct |
693 ms |
72056 KB |
Output is correct |
| 4 |
Correct |
573 ms |
52472 KB |
Output is correct |
| 5 |
Correct |
608 ms |
64504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
634 ms |
66412 KB |
Output is correct |
| 2 |
Correct |
554 ms |
57476 KB |
Output is correct |
| 3 |
Correct |
808 ms |
72092 KB |
Output is correct |
| 4 |
Correct |
815 ms |
71692 KB |
Output is correct |
| 5 |
Correct |
553 ms |
48132 KB |
Output is correct |
| 6 |
Correct |
631 ms |
54684 KB |
Output is correct |
| 7 |
Correct |
443 ms |
46584 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
713 ms |
71988 KB |
Output is correct |
| 3 |
Correct |
693 ms |
72056 KB |
Output is correct |
| 4 |
Correct |
573 ms |
52472 KB |
Output is correct |
| 5 |
Correct |
608 ms |
64504 KB |
Output is correct |
| 6 |
Correct |
634 ms |
66412 KB |
Output is correct |
| 7 |
Correct |
554 ms |
57476 KB |
Output is correct |
| 8 |
Correct |
808 ms |
72092 KB |
Output is correct |
| 9 |
Correct |
815 ms |
71692 KB |
Output is correct |
| 10 |
Correct |
553 ms |
48132 KB |
Output is correct |
| 11 |
Correct |
631 ms |
54684 KB |
Output is correct |
| 12 |
Correct |
443 ms |
46584 KB |
Output is correct |
| 13 |
Correct |
821 ms |
69500 KB |
Output is correct |
| 14 |
Correct |
935 ms |
73872 KB |
Output is correct |
| 15 |
Correct |
576 ms |
60728 KB |
Output is correct |
| 16 |
Correct |
577 ms |
48248 KB |
Output is correct |
| 17 |
Correct |
617 ms |
50168 KB |
Output is correct |
| 18 |
Correct |
846 ms |
82072 KB |
Output is correct |
| 19 |
Correct |
724 ms |
75172 KB |
Output is correct |
| 20 |
Correct |
625 ms |
68728 KB |
Output is correct |
| 21 |
Correct |
660 ms |
64376 KB |
Output is correct |
| 22 |
Correct |
712 ms |
72056 KB |
Output is correct |
| 23 |
Correct |
690 ms |
62456 KB |
Output is correct |
| 24 |
Correct |
712 ms |
59512 KB |
Output is correct |
| 25 |
Correct |
574 ms |
61944 KB |
Output is correct |
