题目链接：https://codeforces.ml/problemset/problem/1250/N

题意：给定很多条边，问如何删除一条边在加上一条边使得所有的边连通
思路：在n个连通块中  每次dfs找到每个连通块的最后一个点，就不要这个点 把这条边连在其他连通块上即可  数据范围需要离散化一下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define pb push_back
 5 const int maxn =2e5+10;
 6 const int mod=1e9+7;
 7 int num[maxn];
 8 vector<pair<int,int>>E[maxn];
 9 int vis[maxn];
10 
11 
12 int n;
13 int tot;
14 map<int,int>mp;
15 
16 int index=-1;
17 int q[maxn];
18 int w[maxn];
19 void dfs(int x)
20 {
21     vis[x]=1;
22     index=x;
23     for(auto &v:E[x])
24     {
25         if(vis[v.first])
26         continue;
27         dfs(v.first);
28     }
29 }
30 
31 
32 
33 
34 int main()
35 {
36     ios::sync_with_stdio(false);
37     cin.tie(0);
38     int t;
39     cin>>t;
40     while(t--)
41     {
42         cin>>n;
43         tot=0;
44         mp.clear();
45         for(int i=1;i<=n;i++)
46         {
47             int x,y;
48             cin>>x>>y;
49             q[i]=x,w[i]=y;
50             if(!mp[x])
51             {
52                 num[++tot]=x;
53                 mp[x]=tot;
54             }
55             if(!mp[y])
56             {
57                 num[++tot]=y;
58                 mp[y]=tot;
59             }
60             E[mp[x]].pb({mp[y],i});
61             E[mp[y]].pb({mp[x],i});
62         }
63 
64         for(int i=1;i<=tot;i++)
65             E[i].clear();
66         for(int i=1;i<=n;i++)
67         {
68             int x=q[i],y=w[i];
69             E[mp[x]].pb({mp[y],i});
70             E[mp[y]].pb({mp[x],i});
71         }
72 
73         for(int i=1;i<=tot;i++)
74             vis[i]=0;
75         vector<int>temp;
76         for(int i=1;i<=tot;i++)
77         {
78             if(vis[i])
79                 continue;
80             index=-1;
81             dfs(i);
82             temp.pb(index);
83         }
84 
85         cout<<temp.size()-1<<'\n';
86         int k=temp[0];
87         for(int i=1;i<temp.size();i++)
88         {
89             int u=temp[i];
90             int w=E[u][0].second;
91             cout<<w<<" "<<num[u]<<" "<<num[k]<<'\n';
92         }
93 
94     }
95 
96 
97 
98 }

View Code