1579. bob 跟 alice心結
type3通用的先弄成component
type1跟type2的從type3做好的繼續弄
看到constrain 1e5
就想直接for進去跟他拼了
1520ms :3333
過了欸好爽 我要來看solution了
醜死勿噴><
class Solution {
public:
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
vector <int> group(n+1, -1);
int gnum;
vector<vector<int>> type1, type2, type3;
int res = 0;
for(auto v: edges){
if(v[0] == 1) type1.push_back(v);
else if(v[0] == 2) type2.push_back(v);
else if(v[0] == 3) type3.push_back(v);
}
vector<unordered_set<int>> t3sc;
for(auto v: type3){
int node1 = -1, node2 = -1;
//v[1] v[2]
//cout << v[1] << ' ' << v[2] << '\n';
for(int i = 0; i < t3sc.size(); i++){
if(t3sc[i].find(v[1]) != t3sc[i].end()) node1 = i;
if(t3sc[i].find(v[2]) != t3sc[i].end()) node2 = i;
if(node1 != -1 and node2 != -1) break;
}
if(node1 == node2){
if(node1 == -1){
//new
//cout << "new\n";
// unordered_set<int> s;
// s.insert(v[1]);
// s.insert(v[2]);
t3sc.push_back(unordered_set<int>({v[1], v[2]}));
}
else{
res++;
}
}
else if(node1 == -1){
t3sc[node2].insert(v[1]);
}
else if(node2 == -1){
t3sc[node1].insert(v[2]);
}
else {
t3sc[node1].insert(t3sc[node2].begin(), t3sc[node2].end());
t3sc.erase(t3sc.begin() + node2);
}
}
cout << "*t3sc " << res << '\n';
for(auto s: t3sc){
for(auto it = s.begin(); it != s.end(); it++){
cout << *it << ' ';
}
cout << '\n';
}
vector<unordered_set<int>> t1sc(t3sc);
for(auto v: type1){
int node1 = -1, node2 = -1;
//v[1] v[2]
//cout << v[1] << ' ' << v[2] << '\n';
for(int i = 0; i < t1sc.size(); i++){
if(t1sc[i].find(v[1]) != t1sc[i].end()) node1 = i;
if(t1sc[i].find(v[2]) != t1sc[i].end()) node2 = i;
if(node1 != -1 and node2 != -1) break;
}
if(node1 == node2){
if(node1 == -1){
//new
//cout << "new\n";
// unordered_set<int> s;
// s.insert(v[1]);
// s.insert(v[2]);
t1sc.push_back(unordered_set<int>({v[1], v[2]}));
}
else{
res++;
}
}
else if(node1 == -1){
t1sc[node2].insert(v[1]);
}
else if(node2 == -1){
t1sc[node1].insert(v[2]);
}
else {
t1sc[node1].insert(t1sc[node2].begin(), t1sc[node2].end());
t1sc.erase(t1sc.begin() + node2);
}
}
cout << "*t1sc " << res << '\n';
for(auto s: t1sc){
for(auto it = s.begin(); it != s.end(); it++){
cout << *it << ' ';
}
cout << '\n';
}
if(t1sc.size() != 1) return -1;
if(t1sc[0].size() != n) return -1;
vector<unordered_set<int>> t2sc(t3sc);
for(auto v: type2){
int node1 = -1, node2 = -1;
//v[1] v[2]
//cout << v[1] << ' ' << v[2] << '\n';
for(int i = 0; i < t2sc.size(); i++){
if(t2sc[i].find(v[1]) != t2sc[i].end()) node1 = i;
if(t2sc[i].find(v[2]) != t2sc[i].end()) node2 = i;
if(node1 != -1 and node2 != -1) break;
}
if(node1 == node2){
if(node1 == -1){
//new
//cout << "new\n";
// unordered_set<int> s;
// s.insert(v[1]);
// s.insert(v[2]);
t2sc.push_back(unordered_set<int>({v[1], v[2]}));
}
else{
res++;
}
}
else if(node1 == -1){
t2sc[node2].insert(v[1]);
}
else if(node2 == -1){
t2sc[node1].insert(v[2]);
}
else {
t2sc[node1].insert(t2sc[node2].begin(), t2sc[node2].end());
t2sc.erase(t2sc.begin() + node2);
}
}
cout << "*t2sc " << res << '\n';
for(auto s: t2sc){
for(auto it = s.begin(); it != s.end(); it++){
cout << *it << ' ';
}
cout << '\n';
}
if(t2sc.size() != 1) return -1;
if(t2sc[0].size() != n) return -1;
return res;
}
};