Znzryb's Blog
0%

ABC-392-E - Cables and Servers 

Posted on Edited on

思路讲解

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

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

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

image

AC代码

https://atcoder.jp/contests/abc392/submissions/62618534

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// 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


*/