Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Codeforces 160D - Edges in MST

問題文 : Edges in MST

概要

$n$ 頂点 $ m $ 辺からなる連結な無向グラフが与えられる.
ある辺がグラフの最小全域木

  • 必ず使われるなら "any"
  • 少なくとも 1 つの最小全域木に使われるなら "at least one"
  • 使われることがなければ "none"

と出力せよ.

制約

  • $1 \leqq n,\ m \leqq 10^5$

解法

クラスカル法のアルゴリズムに従えば, 辺のコストが小さい順に, 連結成分数を減らすような辺であればその辺を採用するというアルゴリズム最小全域木が求まる.
そこで, 同じコストの辺はまとめて連結成分数を減らすかどうか判定すれば良い (あとからまとめて merge してしまえば OK). もし連結成分数を減らすのであればとりあえず "at least one" な辺である.

また, それぞれのコストの辺を追加した時点で, 橋となる辺が "any" となる辺である. 毎回 DFS をして橋を求めるとボトルネックになりそうだが, 連結成分をまとめて 1 つの頂点とすると, 毎回の DFS で訪問する頂点数が $|V| \leqq 2|E|$ より $O(|E|)$ 個になる.

よってこの問題のボトルネックは, クラスカル法でのボトルネックと同じソートになり, これをマージソート等で行うと $O(m \log m)$ 時間でこの問題が解ける.

また, ループ内で巨大な vector を確保すると TLE を引き起こしかねないため, 巨大な vector はうまく使いまして 1 回の確保で済むようにした方が良い.

コード :

#include <bits/stdc++.h>

#define MAX_N (100010)

using namespace std;

class UnionFind {
public :
    UnionFind(int n) : par(n), rank(n, 0){
        for (int i = 0; i < n; i++){
            par[i] = i;
        }
    }
    
    int find(int x){
        return (par[x] == x ? x : par[x] = find(par[x]));
    }
    
    void merge(int x, int y){
        x = find(x);
        y = find(y);
        
        if (x == y) return;
        
        if (rank[x] < rank[y]){
            swap(x, y);
        }
        par[y] = x;
        rank[x] += (rank[x] == rank[y]);
    }
    
    bool isSame(int x, int y){
        return (find(x) == find(y));
    }
    
private :
    vector<int> par;
    vector<int> rank;
};

class Edge {
public :
    Edge(int src, int dst, int cost, int id) :
        src(src), dst(dst), cost(cost), id(id) {}
    
    int src, dst, cost, id;
};

bool operator < (const Edge &a, const Edge &b){
    return (a.cost < b.cost);
}

int res[MAX_N];
const string resType[3] = {"none", "at least one", "any"};

vector<Edge> edges;
vector<pair<int, int> > G[MAX_N];
int numhead[MAX_N], num[MAX_N];

int tm_global;
int ord[MAX_N], low[MAX_N];
bool used[MAX_N];

void getBridge(int v, int id, int &tm)
{
    ord[v] = low[v] = tm++;
    used[id] = true;
    
    for (int i = numhead[v]; i < num[v]; i++){
        if (ord[G[v][i].first] < tm_global){
            getBridge(G[v][i].first, G[v][i].second, tm);
            low[v] = min(low[v], low[G[v][i].first]);
            if (ord[v] < low[G[v][i].first]) res[G[v][i].second] = 2;
        }
        else if (!used[G[v][i].second]){
            low[v] = min(low[v], ord[G[v][i].first]);
            used[G[v][i].second] = true;
        }
    }
}

int main()
{
    int n, m;
    
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back(Edge(a, b, c, i));
    }
    
    sort(edges.begin(), edges.end());
    
    int fst = 0;
    int vpos = 0, vhead = 0;
    int tm = 1;
    UnionFind uft(n + 1);
    vector<pair<pair<int, int>, int> > v(MAX_N);
    
    for (int i = 0; i < m; ){
        
        tm_global = tm;
        
        while (edges[i].cost == edges[fst].cost && i < m){
            int src = uft.find(edges[i].src);
            int dst = uft.find(edges[i].dst);
            if (src != dst){
                v[vpos++] = make_pair(make_pair(src, dst), edges[i].id);
                res[edges[i].id] = 1;
                G[src].push_back(make_pair(dst, edges[i].id));
                G[dst].push_back(make_pair(src, edges[i].id));
                
                num[src]++;
                num[dst]++;
            }
            i++;
        }
        
        for (int j = vhead; j < vpos; j++){
            uft.merge(v[j].first.first, v[j].first.second);
            if (!used[v[j].second]) getBridge(v[j].first.first, v[j].second, tm);
            numhead[v[j].first.first] = num[v[j].first.first];
            numhead[v[j].first.second] = num[v[j].first.second];
        }
        
        vhead = vpos;
        fst = i;
    }
    
    for (int i = 0; i < m; i++){
        printf("%s\n", resType[res[i]].c_str());
    }
    
    return (0);
}