Codeforces Round #286 (Div. 1 B / Div.2 D) - Mr. Kitayuta's Technology

Problem Statement:
506B - Mr. Kitayuta's Technology

Solution:
Very interesting problem. This round indeed has challenging yet amazing problems.

Given a graph G, we want to find the minimum number of edges needed so as to satisfy a certain set of connectivity constraint between M pair of vertices. Let's first consider a simplistic view of the problem: Given a graph G containing N vertices such that G is a direct acyclic graph (DAG), what is the minimum number of directed edges needed to satisfy the connectivity requirements? The answer will always be N-1. Why? Think of topologically sorting the vertices. This DAG can be transformed to a "linked list" DAG: All vertices maintain their relative positions, and for each vertices u, v such that there is no path from u to v and vice versa, we can draw a directed edge from u to v or from v to u (it does not matter!) in our final DAG. Hence in the end we will need N-1 edges!



Next, let's confine ourselves to the case where graph G containing N vertices does not form a DAG. That means there is some cycle or strongly connected components in G. What is the minimum number of edges needed to fulfil the connectivity requirement of such graphs? It will be N edges. Why? Of course we cannot use less than N edges, since then there can't be any cycles since the vertices must be connected. As such the minimum possible will be N, but is it really possible? Yes, because we can simply connect each vertices in a big circle using the N edges, and it will form one big SCC which definitely can fulfil the connectivity requirements.

Now back to the original problem, the graph G given might not necessarily be DAG or cyclical or connected, since there might be some SCC in the graph. Here is a final trick: Let's consider a graph G' in which all directed edges in G is transformed to undirected edges in G'. Now, for each connected component C in G':
1. If vertices in C forms a DAG in G, then the number of edges needed is |C|-1.
2. Otherwise, C has some cycles in G. In this case, we need |C|.
Adding these up, we will arrive at the answer.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

vector<vector<int> > adj, graph;
int N, M;
int vis[100005];
int ff[100005];
int mark[100005];
int color;
int ctr;
vector<int> S;
int low[100005],idx[100005],in_S[100005];
void dfs(int u){
    vis[u] = 1;
    ff[u] = color;
    for(int i=0;i<adj[u].size();++i){
        int v = adj[u][i];
        if(vis[v])continue;
        dfs(v);
    }
}

void scc(int u){
    if(mark[ff[u]])return;
    vis[u] = 1;
    low[u] = ctr;
    idx[u] = ctr;
    ctr++;
    in_S[u] = 1;
    S.push_back(u);
    for(int i=0;i<graph[u].size();++i){
        int v = graph[u][i];
        if(!vis[v]){
            scc(v);
            low[u] = min(low[u], low[v]);
        } else if(in_S[v]){
            low[u] = min(low[u], idx[v]);
        }
        if(mark[ff[u]])return;
    }
    if(low[u] == idx[u]){
        int sz = 0;
        while(!S.empty()){
            int v = S.back();
            S.pop_back();
            ++sz;
            in_S[v] = 0;
            if(v == u)break;
        }
        if(sz > 1){
            mark[ff[u]] = 1;
            return;
        }
    }
}

int main(){
    int u,v;
    scanf("%d%d",&N,&M);
    adj = vector<vector<int> > (N+3);
    graph = vector<vector<int> > (N+3);
    for(int i=0;i<M;++i){
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        graph[u].push_back(v);
    }
    int cc = 0;
    color = 1;
    for(int i=1;i<=N;++i){
        if(vis[i])continue;
        dfs(i);
        ++cc;
        ++color;
    }
    for(int i=1;i<=N;++i)vis[i] = 0;
    ctr = 1;
    for(int i=1;i<=N;++i){
        if(vis[i])continue;
        if(mark[ff[i]])continue;
        scc(i);
        cc -= mark[ff[i]];
    }
    printf("%d\n",N-cc);
    return 0;
}