1236:Network of Schools

keyword

有向グラフ　強連結成分分解　C++

概要

ノード数V(<100)の有向グラフが与えられる。このとき、(1)全てのノードに情報を伝達するには最大でいくつのノードに情報を流せばよいか。(2)任意の点に情報を与えたとき全てのノードに情報が伝わるようにしたい、最小で何本の辺を追加すればよいか。をそれぞれ求める問題。
なにはともあれ強連結成分分解してDAGに落とす。落とした上で、(1)はDAGのsourceの個数であり、(2)はそのDAGを一つの強連結成分にするのに必要な辺の最小化、とそれぞれ読み替える。(1)は簡単。(2)は、まず連結成分を環状につなぎ、あまったsourceとsinkをつなげばよい。なので、答えはsource、sink、連結成分の個数をそれぞれA,B,Cとすると、C+max(A-C, B-C) = max(A, B)。ただし強連結成分が一つしかないときは例外なので注意。計算量O(V+E)。ソースには余計なものが入っています。

vector<int> graph[102];
vector<int> revGraph[102];
bool visited[102];
int cmp[102];
int cmp2[102];
vector<int> st;
int N;

void dfs2(int v){
    visited[v] = true;
    for(int i=0; i<graph[v].size(); i++){
        int u = graph[v][i];
        if(!visited[u])
            dfs2(u);
    }
    for(int i=0; i<revGraph[v].size(); i++){
        int u = revGraph[v][i];
        if(!visited[u])
            dfs2(u);
    }
}

void dfs(int v){
    visited[v] = true;
    for(int i=0; i<graph[v].size(); i++){
        int u = graph[v][i];
        if(!visited[u])
            dfs(u);
    }
    st.push_back(v);
}

void revDfs(int v, int k){
    visited[v] = true;
    for(int i=0; i<revGraph[v].size(); i++){
        int u = revGraph[v][i];
        if(!visited[u])
            revDfs(u, k);
    }
    if(k>=0)
        cmp[v] = k;
}

int SCC(){
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<N; i++)if(!visited[i])
        dfs(i);
    memset(visited, 0, sizeof(visited));
    int ret = 0;
    while(!st.empty()){
        int v = st.back(); st.pop_back();
        if(!visited[v]){
            revDfs(v,ret);
            ret++;
        }
    }
    return ret;
}

void solve(){
    int k = SCC();
    vector<int> vs(k);
    vector<int> isSource(k, false), isSink(k,false);
    int ansA = 0, ansB = 0;
    for(int i=0; i<N; i++){
        vs[cmp[i]] = i;
    }
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<k; i++)if(!visited[vs[i]]){
        dfs(vs[i]);
        isSource[i] = true;
    }
    memset(visited, 0, sizeof(visited));
    for(int i=k-1; i>=0; i--)if(!visited[vs[i]]){
        revDfs(vs[i],-1);
        isSink[i] = true;
    }
    int cnt = 0;
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<k; i++)if(!visited[vs[i]]){
        dfs2(vs[i]);
        cnt++;
    }
    for(int i=0; i<k; i++)if(isSource[i]) ansA++;
    if(k!=1){
        for(int i=0; i<k; i++)if(isSink[i])ansB++;
        ansB = max(ansA, ansB);
    }
    printf("%d\n%d\n",ansA, ansB);
}