学步园

这题的意思是有一个城市可以发送和接收信息 把城市看成点 给m条边 单向图  问：删去一个点后 最大的一个强连通中的个数最小是多少。

我用的暴力做法 考虑到n<=100 暴力遍历

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 110
int sum[MAXN],stack[MAXN],dfn[MAXN],low[MAXN],times,top,m,n;
bool instack[MAXN];
int scan;
vector <int> e[MAXN];
void init(){

    memset(instack,0,sizeof(instack));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    times=top=sum[0]=0;
}
void tarjan(int u){
    if(u==scan)return ;
    dfn[u]=low[u]=++times;
    stack[top++]=u;
    instack[u]=true;
    for(int i=0;i<(int)e[u].size();i++){
        int v=e[u][i];
        if(v==scan)continue;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        ++sum[0];
        int tot=0;
        do{
            u=stack[--top];
            instack[u]=false;
            ++tot;
        }while(dfn[u]!=low[u]);
        sum[sum[0]]=tot;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<MAXN;i++)e[i].clear();
        for(int i=0,x,y;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            e[x+1].push_back(y+1);
        }
        /*
        for(int i=1;i<=n;i++)
            if(!dfn[i])tarjan(i);
                */
            /*
        printf("一共有%d个强连通\n",sum[0]);
        for(int i=1;i<=sum[0];i++)
            printf("%d ",sum[i]);
        puts("");
        */
        int minn= 1000000000;
        int count0;
        for(int i=1;i<=n;i++){
            scan=i;
            init();
            for(int j=1;j<=n;j++)
                if(!dfn[j])tarjan(j);
            int maxn=-1;
            int count1;
            for(int j=1;j<=sum[0];j++)
            {
                if(maxn<sum[j]){
                    maxn=sum[j];
                    count1=0;
                }
                if(maxn==sum[j])++count1;
            }
            if(maxn<minn){
                minn=maxn;
                count0=count1;
            }
        }
        //printf("minn:%d\n",minn);
        if(minn<2)printf("%d\n",0);
        else printf("%d\n",minn);
    }
    return 0;
}