Re: [閒聊] 每日leetcode

[sixB (6B)]

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;
    }
};
-----
Sent from JPTT on my iPad

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719781246.A.2E3.html