Submission #62358247

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define UFLIMIT (2<<17)
int unicnt[UFLIMIT];
vector<vector<array<int,3>>>amari; // add
void ufinit(int n){
	for(int i=0;i<n;i++)unicnt[i]=1;
	amari.resize(n); // add
}
int ufroot(int x){return unicnt[x]<=0?-(unicnt[x]=-ufroot(-unicnt[x])):x;}
int ufsame(int x,int y){return ufroot(x)==ufroot(y);}
void uni(int x,int y){
	if((x=ufroot(x))==(y=ufroot(y)))return;
	if(unicnt[x]<unicnt[y])swap(x,y);
	unicnt[x]+=unicnt[y];
	unicnt[y]=-x;
	amari[x].insert(amari[x].end(),amari[y].begin(),amari[y].end()); // add
	amari[y].clear(); // add
}
#undef UFLIMIT


int main(){
	int n,m;
	cin >> n >> m;

	ufinit(n);
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		x--,y--;
		if(ufsame(x,y)){
			amari[ufroot(x)].push_back({x,y,i});
		}else{
			uni(x,y);
		}
	}

	vector<pair<int,int>>cc;
	for(int i=0;i<n;i++)if(ufroot(i)==i)cc.push_back({amari[i].size(),i});
	sort(cc.rbegin(),cc.rend());
	
	cout << cc.size()-1 << endl;

	int pos=1;
	for(auto[_, root]:cc){
		for(auto[x,y,i]:amari[root]){
			if(pos<cc.size()){
				cout << i+1 << ' ' << x+1 << ' ' << cc[pos++].second+1 << endl;
			}
		}
	}
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:49:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   49 |                         if(pos<cc.size()){
      |                            ~~~^~~~~~~~~~

Judge Result