题面
(T) 组测试数据。每次给一个 (n) 边形的三角剖分，求节点顺序和剖分顺序。
数据范围：(3le nle 10^5)，(sum nle 10^5)。
蒟蒻解
这题在炫酷的代码和外表下是一个大水题。
对于每一个剖下来的三角形的边，要么是原多边形的边，要么是割的边。
多边形的边在所有三角形的边中出现 (1) 次，割边在所有三角形中出现 (2) 次。
所以用 map 记录每条边的出现次数。
然后从一个三角形出发，然后用 dfs 合并上出现 (2) 次的边的三角形即可。
对于第一个询问可以用一个环状链表，第二个可以回溯加 vector。
为了不方便，代码中从一个有两条原多边形的边的三角形开始，这样每次就最多有两边要合并三角形了。
代码
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
#define be(a) (a).begin()
#define en(a) (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)
#define L(i,a,b) for(int i=(b)-1,I=(a)-1;i>I;i--)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e5;
int n,nex[N],ea[N-2],eb[N-2],ec[N-2];
bool vis[N]; vector<int> ans;
map<pair<int,int>,vector<pair<int,int>>> mp;
#define pa(x,y) mp(min(x,y),max(x,y))
#define an(x,y) mp[pa(x,y)]
//Main
void solve(pair<int,int> e){
if(nex[e.y]==e.x) swap(e.x,e.y);
vector<pair<int,int>> tv=an(e.x,e.y);
int ez=vis[tv[0].x]?tv[1].x:tv[0].x;
int et=vis[tv[0].x]?tv[1].y:tv[0].y;
vis[ez]=true,nex[e.x]=ez,nex[ez]=e.y;
if(sz(an(e.x,ez))>=2) solve(mp(e.x,ez));
if(sz(an(e.y,ez))>=2) solve(mp(e.y,ez));
ans.pb(et);
}
void Main(){
cin>>n,ans.clear();
fill(nex,nex+n,-1);
fill(vis,vis+n,false);
if(n==3){
cin>>ea[0]>>eb[0]>>ec[0];
cout<<"1 2 3
1
";
return;
}
mp.clear();
R(i,0,n-2){
cin>>ea[i]>>eb[i]>>ec[i];
--ea[i],--eb[i],--ec[i];
an(ea[i],eb[i]).pb(mp(ec[i],i));
an(ea[i],ec[i]).pb(mp(eb[i],i));
an(eb[i],ec[i]).pb(mp(ea[i],i));
}
int s=-1; pair<int,int> e(-1,-1);
R(i,0,n-2){
int cnt=0;
if(sz(an(ea[i],eb[i]))==2) cnt++,e=pa(ea[i],eb[i]);
if(sz(an(ea[i],ec[i]))==2) cnt++,e=pa(ea[i],ec[i]);
if(sz(an(eb[i],ec[i]))==2) cnt++,e=pa(eb[i],ec[i]);
if(cnt==1){s=i;break;}
}
nex[ea[s]]=eb[s],nex[eb[s]]=ec[s],nex[ec[s]]=ea[s];
vis[ea[s]]=vis[eb[s]]=vis[ec[s]]=true,ans.pb(s);
solve(e);
int now=0;
R(i,0,n) cout<<now+1<<' ',now=nex[now];cout<<'
';
for(int x:ans) cout<<x+1<<' ';cout<<'
';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int tn; cin>>tn;
R(ta,0,tn) Main();
return 0;
}
祝大家学习愉快！