https://codeforces.com/problemset/problem/1250/N
这场vp到2个半小时机房断网了。。。C都没来得及写。。。。这题也没调。。。
这题当时WA43，大致思路就是把联通块找出来，然后把其他连通块都连向第一个连通块
对于如果这个连通块存在du为1的点，那么我们就舍弃这个点，把这条边连向第一个连通块
如果不存在，我比赛的时候脑抽以为因为du全都>=2所以每个点都是在环上所以可以随便选，其实是du>=2也有可能是割点，任选一条边有可能选到割边的，所以只需要在dfs的时候记录一下这个联通分量中的任意一条环上的边就行了。
#include<bits/stdc++.h> #define maxl 200010 using namespace std; int n,m,cnt,tot,fcnt; int num[maxl],ehead[maxl],du[maxl],huan[maxl]; vector<int> f[maxl]; struct edge { int u,v; }inie[maxl]; struct ed { int to,nxt,id; }e[maxl<<1]; bool vis[maxl]; struct q { int id,a,b; }ans[maxl]; inline void add(int u,int v,int id) { e[++cnt].to=v;e[cnt].id=id; e[cnt].nxt=ehead[u];ehead[u]=cnt; } inline void dfs(int u,int fa) { vis[u]=true;f[fcnt].push_back(u); int v; for(int i=ehead[u];i;i=e[i].nxt) { v=e[i].to; if(v==fa) continue; if(vis[v]) huan[fcnt]=e[i].id; else dfs(v,u); } } inline void prework() { scanf("%d",&m); int u,v;tot=0; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); inie[i]=edge{u,v}; num[++tot]=u; num[++tot]=v; } sort(num+1,num+1+tot); n=unique(num+1,num+1+tot)-num-1; for(int i=1;i<=n;i++) ehead[i]=0,du[i]=0,vis[i]=false; cnt=0; for(int i=1;i<=m;i++) { u=lower_bound(num+1,num+1+n,inie[i].u)-num; v=lower_bound(num+1,num+1+n,inie[i].v)-num; add(u,v,i);add(v,u,i); du[u]++;du[v]++; } for(int i=1;i<=fcnt;i++) f[i].clear(); fcnt=0; for(int i=1;i<=n;i++) if(!vis[i]) { fcnt++; dfs(i,0); } } inline void mainwork() { if(fcnt==1) return; else { int u,v,l; for(int i=2;i<=fcnt;i++) { l=f[i].size();u=-1; for(int j=0;j<l;j++) if(du[f[i][j]]==1) u=f[i][j]; if(u>0) { ans[i-1].id=e[ehead[u]].id; ans[i-1].a=num[u]; ans[i-1].b=num[f[1][0]]; } else { ans[i-1].id=huan[i]; ans[i-1].a=inie[huan[i]].u; ans[i-1].b=num[f[1][0]]; } } } } inline void print() { if(fcnt==1) puts("0"); else { printf("%d\n",fcnt-1); for(int i=1;i<=fcnt-1;i++) printf("%d %d %d\n",ans[i].id,ans[i].a,ans[i].b); } } int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { prework(); mainwork(); print(); } return 0; }
