一个比较显然的思路就是：我们按照右端点从小到大的顺序（右端点相同按左端点从大到小）去考虑每个好的区间。
由于是连通性问题，不难想到用并查集去实时维护连通性。
根据定义，一个好的区间必定对应了一个连通块；我们考虑的是好的区间，所以当前并查集中的每个连通块必定都是一个区间。而在加入某个点前，这个连通块可能是好几个更小的连通块。换句话说，是区间中的某个点，串联起了其它连通块。
有了上述思维方向的转化，正解也就比较自然了。一个区间由好几个子区间组成，假设它们为 \([l_1,r_1],[l_2,r_2],\dots,[l_m,r_m]\)。不妨采取分类讨论进行构造（假设当前的区间为 \([l,r]\)）：
-
\(m=1\)
当前区间已经连通，不作处理。
-
\(m=2\)
连接 \((l,r)\)。
-
\(m=3\)
此时无解。必须得放到更大的区间里去处理才会有解。
-
\(m>3\)
连接 \((l,r),(l,r_{m-1})\)，以及 \((r_{2},r),(r_{3},r),\dots,(r_{m-2},r)\)。
注意区间拆分中的 \(l_1\) 就是 \(l\)，\(r_m\) 即为 \(r\)。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
const int N = 2010;
int n, t, fa[N]; char e[N][N];
void solve(){
scanf("%d", &n);
FL(i, 1, n) scanf("%s", e[i] + (fa[i] = i));
FL(j, 1, n) FR(i, j - 1, 1){
if(fa[j] <= i || e[i][j] == '0') continue;
printf("%d %d\n", i, j);
if((t = fa[fa[j] - 1]) > i){
printf("%d %d\n", i, fa[j] - 1);
for(int u = t - 1; fa[u] > i; u = fa[u] - 1)
printf("%d %d\n", fa[u], j);
}
FR(k, j, i){
if(fa[k] == i) break;
fa[k] = fa[i];
}
}
}
int main(){
int T; scanf("%d", &T);
while(T--) solve();
return 0;
}