ABC-392-E - Cables and Servers · znzryb

## 思路讲解

为什么这道题目可以用类似于双指针的东西做出来？

其实有点类似于我最早的思路，就是已经合并过的就不管了。

不过他是以边为主视角的，这个还是比较新颖的，我之前的都是以块为主视角的，但块存在自环，重边，没边等等情况，总之肯定没有以边为主视角方便。

![image](https://media.znzryb.com/20250209-b4ea151f/image_98ec3af8.png)

## AC代码

[https://atcoder.jp/contests/abc392/submissions/62618534](https://atcoder.jp/contests/abc392/submissions/62618534)

```cpp
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T;
vector<pll> g[MAXN];
pll ab[MAXN];
bool isRem[MAXN];

struct DSU {  // referred jiangly
  int fa[MAXN], siz[MAXN], ln;
  DSU(int n) {
    ln = n;
    FOR(i, 1, n) {
      fa[i] = i;
      siz[i] = 1;
    }
  }
  int find(int x) {
    while (fa[x] != x) {
      x = fa[x];
      fa[x] = fa[fa[x]];
    }
    return x;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    siz[x] += siz[y];
    fa[y] = x;
    return true;
  }
  int size(int x) { return siz[find(x)]; }
  int countFa() {
    int res = 0;
    FOR(i, 1, ln) {
      if (fa[i] == i) ++res;
    }
    return res;
  }
};

inline void solve() {
  cin >> N >> M;
  DSU dsu(N);
  FOR(i, 1, M) {
    cin >> ab[i].fi >> ab[i].se;
    if (!dsu.merge(ab[i].fi, ab[i].se)) {  // 说明这条边是多余的
      isRem[i] = true;
    }
  }
  ll ans = dsu.countFa() - 1;
  ll flag = 1;
  cout << ans << '\n';
  FOR(i, 1, M) {
    if (ans <= 0) break;
    if (isRem[i]) {  // 只有多余的边才会进入
      FOR(j, flag, N) {
        if (!dsu.same(ab[i].fi, j)) {
          flag = j + 1;
          cout << i << ' ' << ab[i].se << ' ' << j << '\n';
          dsu.merge(ab[i].fi, j);
          --ans;
          break;
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
/*
AC
https://atcoder.jp/contests/abc392/submissions/62618534
*/
```

## 心路历程（WA，TLE，MLE……）

直接遍历还是有风险，合并还是要用dsu

```cpp
// Problem: E - Cables and Servers
// Contest: AtCoder - Japan Registry Services (JPRS) Programming Contest 2025#1 (AtCoder Beginner Contest 392)
// URL: https://atcoder.jp/contests/abc392/tasks/abc392_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
vector<pll> g[MAXN];
ll fa[MAXN];
bool vis[MAXN];
vector<ll> root;
vector<pll> rem[MAXN];
pll ab[MAXN];

inline ll find(ll x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void dfs(ll x,ll pa){
	vis[x]=true;
	FOR(i,0,SZ(g[x])-1){
		ll fx=g[x][i].fi;
		if(vis[fx]) {
			// cerr<< fx <<' '<<pa<<'\n';
			if(fx!=pa) rem[find(fx)].pb({ab[g[x][i].se].se,g[x][i].se});
			continue;
		}
		fa[fx]=find(x);
		dfs(fx,x);
	}
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		ll a,b;
		cin>>a>>b;
		ab[i].fi=a,ab[i].se=b;
		if(a!=b){
			g[a].pb({b,i});
			g[b].pb({a,i});
		}else{
			g[a].pb({b,i});
		}
	}
	FOR(i,1,N){
		fa[i]=i;
	}
	
	FOR(i,1,N){
		if(vis[i]) continue;
		// cerr<<"OK\n";
		dfs(i,0);
	}
	set<ll> disCot;
	FOR(i,1,N){
		if(fa[i]==i) root.push_back(i),disCot.insert(i);
	}
	cout<<SZ(root)-1<<'\n';
	if(SZ(root)-1==0) return;
	disCot.erase(1);
	FOR(i,0,root.size()-1){
		if(disCot.empty()){
			break;
		}
		ll ri=root[i],start=0;
		if(SZ(rem[ri])>0){
			if(disCot.find(ri)!=disCot.end()){
				if(ri!=1) cout<<rem[ri][0].se<<' '<<rem[ri][0].fi<<' '<<1<<'\n',start=1;
				disCot.erase(ri);
			}
		}
		FOR(j,start,SZ(rem[ri])-1){
			if(disCot.empty()) return;
			cout<<rem[ri][j].se<<' '<<rem[ri][j].fi<<' '<< *disCot.begin()  <<'\n';
			disCot.erase(disCot.begin());	// 一定要在删之前判断是否为空
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	
	// FOR(i,1,N){
		// cerr<<i<<":\n";
		// FOR(j,0,SZ(rem[i])-1){
			// cerr<<rem[i][j].fi<<' '<< rem[i][j].se<<'\n';
		// }
		// cerr<<'\n';
	// }	
	return 0;
}
/*
WA*9
https://atcoder.jp/contests/abc392/submissions/62570130
排除返祖边处理问题
8 8
1 2
1 3
1 3
4 5
5 6
6 8
8 7
7 5

1
3 3 4


排除连接问题（有的联通块未连接）
6 5
1 2
1 2
1 3
5 6
5 6

2
2 2 4
5 6 1


*/
```