[强连通分量]LightOJ 1210 - Efficient Traffic System

传送门：http://lightoj.com/volume_showproblem.php?problem=1210

1210 - Efficient Traffic System

PDF (English)

Statistics

Forum

Time Limit:2 second(s)

Memory Limit:32 MB

I was given the task to make all the major two way roads in Bangladesh into one way roads. And I have done that easily with some great pruning. And I asked the Govt. Traffic Management System to change the direction of all the roads.

But after some days, I realized that I should have thought of the fact that all cities should be reachable from other cities using the existing one way roads. Since the traffic system is already designed, so it may not be changed. But I can ask the govt. to build new roads between any pair of cities.

Now since the task looks quite hard for me, I am asking you to do it for me. I will give you the current roads configuration. You have to find the minimum number of roads that have to be built such that it's possible to go from any city to any other city.

Input

Input starts with an integerT (≤ 25), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integersn (1 ≤ n ≤ 20000)andm (0 ≤ m ≤ 50000), wherendenotes the number of cities andmdenotes the number of one way roads. Each of the nextmlines contains two integersu v (1 ≤ u, v ≤ n, u ≠ v)meaning that there is a road fromutov. Assume that there can be at most one road from a cityutov.

Output

For each case, print the case number and the minimum number of roads that have to be built.

Sample Input	Output for Sample Input
2 3 0 3 2 1 2 1 3	Case 1: 3 Case 2: 2

Note

Dataset is huge. Use faster I/O methods.

---

SPECIAL THANKS: JANE ALAM JAN (DESCRIPTION, SOLUTION, DATASET)

题意：给定一个有向图，问最少加几条边使得图成为SCC。

前面做过一遍了，当是复习吧，具体分析参加前面一篇博客。http://blog.csdn.net/airarts_/article/details/7348817

注意求度的时候需要遍历所有的边，所以DFS中计算度的位置要摆正确。。

代码：

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 22222;
int low[MAXN],dfn[MAXN],ind[MAXN],outd[MAXN],belong[MAXN],t,n,m,deep,scc;
vector<int> g[MAXN];
stack<int> s;
void init(){
    memset(dfn,-1,sizeof(dfn));
    memset(ind,0,sizeof(ind));
    memset(outd,0,sizeof(outd));
    memset(belong,-1,sizeof(belong));
    scc = deep = 0;
    for(int i=0;i<MAXN;i++)g[i].clear();
    while(!s.empty())s.pop();
}
void tarjan(int u){
    low[u] = dfn[u] = deep++;
    s.push(u);
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(dfn[v]==-1){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }else if(belong[v]==-1){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        int v;
        do{
            v = s.top();
            s.pop();
            belong[v]=scc;
        }while(v!=u);
        //cout<<scc<<" "<<u<<endl;
        scc++;
    }
}
void DFS(int u){
    dfn[u] = 1;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        if(belong[u]!=belong[v]){
                outd[belong[u]]++;
                ind[belong[v]]++;
        }
        if(!dfn[v]){
            DFS(v);
        }
    }
}
int solve(){
    if(scc==1)return 0;
    int maxi=0,maxo=0;
    for(int i=0;i<scc;i++){
        if(!outd[i])maxo++;
        if(!ind[i])maxi++;
    }
    //cout<<maxo<<" "<<maxi<<endl;
    return max(maxi,maxo);
}
int main(){
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d%d",&n,&m);init();
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            a--,b--;
            g[a].push_back(b);
        }
        for(int i=0;i<n;i++)if(dfn[i]==-1)tarjan(i);
        memset(dfn,0,sizeof(dfn));
        //for(int i=0;i<n;i++)cout<<belong[i]<<endl;
        for(int i=0;i<n;i++)if(!dfn[i])DFS(i);
        printf("Case %d: %d\n",cas,solve());
    }
    return 0;
}