2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛 F. Islands（有向图加边变成一个强连通图）

约定不等于承诺〃 2022-06-08 00:45 130阅读 0赞

On the mysterious continent of Tamriel, there is a great empire founded by human.

To develope the trade, the East Empire Company is set up to transport goods from place to place.

Recently, the company wants to start their business in Solstheim, which is consists of N*N*islands.

Luckily, there are already M*M* sea routes.

All routes are one-way, and the i*i*\-th route can transport person and goods from island u\_i*u**i* to v\_i*v**i*.

Now, the company nominates you a particular job to plan some new routes to make sure that person and goods can be transported between any two islands.

Furthermore, because the neighboring regions are under attack by an increasing number of dragons, limited resources can be used to set up new routes.

So you should plan to build new routes as few as possible.

### Input Format ###

The first line contains an integer T*T*, indicating that there are T*T* test cases.

For each test case, the first line includes two integers N~(N \\leq 10000)*N*(*N*≤10000) and M~(M \\leq 100000)*M*(*M*≤100000), as described above.

After that there are M*M* lines. Each line contains two integers u\_i*u**i* and v\_i*v**i*.

### Output Format ###

For each test case output one integer, represent the least number of routes required to new.

#### 样例输入 ####

2
    4 3
    1 2
    2 3
    3 4
    4 4
    1 2
    1 4
    3 2
    3 4

#### 样例输出 ####

1
    2

题解：

比赛的时候隐隐约约记得这是强连通图的内容。。。然后因为没怎么练这一块就不知道怎么做，然后百度了一个模板。。。

然后震惊了，发现一题一模一样的题目，就是换了种说法 ：hdu2767，一模一样的题。。然后直接复制了代码，改了下数据范围。。ac了

hhhhhh别打我我之后会好好学这部分内容的

附上救世主博客：[http://blog.csdn.net/u013167299/article/details/48023495][http_blog.csdn.net_u013167299_article_details_48023495]

完全复制的代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<string>
    #include<cstring>
    #include<stack>
    #include<queue>
    #include<vector>
    #include<cstdlib>
    #define lson (rt<<1),L,M
    #define rson (rt<<1|1),M+1,R
    #define M ((L+R)>>1)
    #define cl(a,b) memset(a,b,sizeof(a));
    #define LL long long
    #define P pair<int,int>
    #define X first
    #define Y second
    #define pb push_back
    #define fread(zcc)  freopen(zcc,"r",stdin)
    #define fwrite(zcc) freopen(zcc,"w",stdout)
    using namespace std;
    const int maxn=100005;
    const int inf=999999;
    
    vector<int> G[maxn];
    int low[maxn],dfn[maxn],belong[maxn],s[maxn];
    bool ins[maxn];
    int cnt,num,top;
    
    void dfs(int u){
        dfn[u]=low[u]=++num;
        s[++top]=u;
        ins[u]=true;
        int N=G[u].size();
        for(int i=0;i<N;i++){
            int v=G[u][i];
            if(!dfn[v]){
                dfs(v);
                low[u]=min(low[u],low[v]);
            }
            else if(ins[v]&&dfn[v]<low[u]){
                low[u]=dfn[v];
            }
        }
        if(dfn[u]==low[u]){
            int v;
            cnt++;
            do{
                v=s[top--];
                ins[v]=false;
                belong[v]=cnt;
            }while(u!=v);
        }
    }
    void Tarjan(int n){
        cnt=num=top=0;
        cl(belong,0);
        cl(ins,false);
        cl(dfn,0);
        for(int i=1;i<=n;i++){
            if(!dfn[i])dfs(i);
        }
    }
    
    int in[maxn],out[maxn];
    int main(){
        int T;
        int n,m;
        scanf("%d",&T);
        while(T--){
            int n,m;
            scanf("%d%d",&n,&m);
            if(m==0){
                printf("%d\n",n);continue;
            }
            for(int i=0;i<=n;i++)G[i].clear();
            for(int i=0;i<m;i++){
                int x,y;
                scanf("%d%d",&x,&y);
                G[x].pb(y);
            }
    
            Tarjan(n);
            if(cnt<=1){//特判
                printf("0\n");continue;
            }
            cl(in,0);
            cl(out,0);
            for(int i=1;i<=n;i++){//进行缩点，在一个强连通的中的点，看为一个
                for(int j=0;j<G[i].size();j++){
                    if(belong[i]!=belong[G[i][j]]){
                        in[belong[G[i][j]]]++;
                        out[belong[i]]++;
                    }
                }
            }
            int xx=0,yy=0;
            for(int i=1;i<=cnt;i++){
                if(!in[i])xx++;
                if(!out[i])yy++;
            }
            printf("%d\n",max(xx,yy));
        }
        return 0;
    }

[http_blog.csdn.net_u013167299_article_details_48023495]: http://blog.csdn.net/u013167299/article/details/48023495