結果

問題 No.416 旅行会社
ユーザー Hachimori
提出日時 2016-08-26 23:11:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 633 ms / 4,000 ms
コード長 3,006 bytes
コンパイル時間 1,056 ms
コンパイル使用メモリ 79,596 KB
実行使用メモリ 15,468 KB
最終ジャッジ日時 2024-12-14 19:49:33
合計ジャッジ時間 8,255 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#define bgnE first
#define endE second
using namespace std;
const int BUF = 100005;
typedef pair<int, int> Edge;


class DisjointSet {
private:
    int node2group[BUF];
    vector<vector<int> > group2node;

public:
    DisjointSet() {}
    
    DisjointSet(int n) {
        group2node = vector< vector<int> >(n);
        
        for (int i = 0; i < n; ++i) {
            node2group[i] = i;
            group2node[i].push_back(i);
        }
    }

    void merge(int a, int b) {
        if (find(a) != find(b)) {
            vector<int> &groupA = findGroup(a);
            vector<int> &groupB = findGroup(b);

            if (groupA.size() < groupB.size()) {
                while (!groupA.empty()) {
                    groupB.push_back(groupA.back());
                    groupA.pop_back();
                }
                node2group[find(a)] = find(b);
            }
            else {
                while (!groupB.empty()) {
                    groupA.push_back(groupB.back());
                    groupB.pop_back();
                }
                node2group[find(b)] = find(a);
            }
        }
    }

    int find(int a) {
        if (node2group[a] == a) return a;
        return node2group[a] = find(node2group[a]);
    }

    vector<int>& findGroup(int a) {
        return group2node[find(a)];
    }
};


int nNode;
set<Edge> availEdges;
vector<Edge> removeEdgeOrder;

void read() {
    availEdges.clear();
    removeEdgeOrder.clear();

    int nEdge, nQuery;
    cin >> nNode >> nEdge >> nQuery;

    for (int i = 0; i < nEdge; ++i) {
        int s, t;
        cin >> s >> t;
        --s;
        --t;
        availEdges.insert(Edge(s, t));
    }

    for (int i = 0; i < nQuery; ++i) {
        int s, t;
        cin >> s >> t;
        --s;
        --t;
        availEdges.erase(Edge(s, t));
        removeEdgeOrder.push_back(Edge(s, t));
    }
}


void work() {
    static DisjointSet dset;
    dset = DisjointSet(nNode);

    for (set<Edge>::iterator it = availEdges.begin(); it != availEdges.end(); ++it) {
        Edge edge = *it;
        dset.merge(edge.bgnE, edge.endE);
    }

    static int ans[BUF];
    for (int i = 0; i < nNode; ++i) {
        if (dset.find(0) == dset.find(i)) {
            ans[i] = -1;
        }
    }

    for (int i = removeEdgeOrder.size() - 1; i >= 0; --i) {
        Edge &addEdge = removeEdgeOrder[i];

        if (dset.find(0) == dset.find(addEdge.endE)) {
            swap(addEdge.bgnE, addEdge.endE);
        }

        if (dset.find(0) == dset.find(addEdge.bgnE) && dset.find(0) != dset.find(addEdge.endE)) {
            vector<int> &joinedGroup = dset.findGroup(addEdge.endE);
            for (int j = 0; j < joinedGroup.size(); ++j) {
                ans[joinedGroup[j]] = i + 1;
            }
        }
        dset.merge(addEdge.bgnE, addEdge.endE);
    }

    for (int i = 1; i < nNode; ++i) {
        cout << ans[i] << endl;
    }
}


int main() {
    read();
    work();
    return 0;
}
0