#include <bits/stdc++.h>
using namespace std;
bool static cmp(vector<int>& a, vector<int>& b)
{
return a[0] > b[0];
}
int find(int x, vector<int>& parent)
{
if (parent[x] == x)
return x;
return parent[x] = find(parent[x], parent);
}
bool union1(int x, int y, vector<int>& parent,
vector<int>& rank)
{
int lx = find(x, parent);
int ly = find(y, parent);
if (lx != ly) {
if (rank[lx] > rank[ly]) {
parent[ly] = lx;
}
else if (rank[lx] < rank[ly]) {
parent[lx] = ly;
}
else {
parent[lx] = ly;
rank[ly] += 1;
}
return true;
}
return false;
}
int removeMaxEdges(int n, vector<vector<int> >& edges)
{
int n1 = n + 1;
sort(edges.begin(), edges.end(), cmp);
vector<int> parentA(n1), parentB(n1), rankA(n1),
rankB(n1);
for (int i = 1; i <= n; i++) {
parentA[i] = i;
parentB[i] = i;
rankA[i] = 1;
rankB[i] = 1;
}
int connectedComponentA = n, connectedComponentB = n,
remove = 0;
for (auto i : edges) {
if (i[0] == 2) {
bool mergeA
= union1(i[1], i[2], parentA, rankA);
bool mergeB
= union1(i[1], i[2], parentB, rankB);
if (mergeA) {
connectedComponentA--;
}
if (mergeB) {
connectedComponentB--;
}
if (mergeA == false && mergeB == false) {
remove++;
}
}
else if (i[0] == 1) {
bool mergeA
= union1(i[1], i[2], parentA, rankA);
if (mergeA) {
connectedComponentA--;
}
if (mergeA == false) {
remove++;
}
}
else {
bool mergeB
= union1(i[1], i[2], parentB, rankB);
if (mergeB) {
connectedComponentB--;
}
if (mergeB == false) {
remove++;
}
}
}
if (connectedComponentA != 1
|| connectedComponentB != 1) {
return -1;
}
return remove;
}
int main()
{
int N = 4;
vector<vector<int> > edges
= { { 0, 1, 2 }, { 0, 3, 4 }, { 1, 1, 2 }, { 1, 2, 4 }, { 2, 1, 2 }, { 2, 1, 3 } };
cout << removeMaxEdges(N, edges);
return 0;
}
Stay connected with us on social media platform for instant update click here to join our Twitter, & Facebook We are now on Telegram. Click here to join our channel (@TechiUpdate) and stay updated with the latest Technology headlines. For all the latest Technology News Click Here