主题链接:

http://acm.hdu.edu.cn/showproblem.php?

pid=3836

Equivalent Sets

Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 104857/104857 K (Java/Others)

Total Submission(s): 2890    Accepted Submission(s): 1006

4 0

3 2

1 2

1 3

4

2

Hint

Case 2: First prove set 2 is a subset of set 1 and then prove set 3 is a subset of set 1.

Statistic | Submit | 

problemid=3836" style="color:rgb(26,92,200); text-decoration:none">Discuss

求至少须要增添多少条边，使得该图为强连通图。

解题思路：

tarjan求强连通。然后统计入度为0和出度为0的强连通分量个数，两者的最大值即为答案。

代码：

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#include<cmath>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 21000

int low[Maxn],dfn[Maxn],dindex,n;

int sta[Maxn],belong[Maxn],bcnt,ss;

bool iss[Maxn];

int de1[Maxn],de2[Maxn];

vector<vector<int> >myv;

void tarjan(int cur)

{

    //printf(":%d\n",cur);

    //system("pause");

    int ne;

    dfn[cur]=low[cur]=++dindex;

    iss[cur]=true;

    sta[++ss]=cur;

    for(int i=0;i<myv[cur].size();i++)

    {

        ne=myv[cur][i];

        if(!dfn[ne])

        {

            tarjan(ne);

            low[cur]=min(low[cur],low[ne]);

        }

        else if(iss[ne]&&dfn[ne]<low[cur])

            low[cur]=dfn[ne];

    }

    if(dfn[cur]==low[cur])

    {

        bcnt++;

        do

        {

            ne=sta[ss--];

            iss[ne]=false;

            belong[ne]=bcnt;

        }while(ne!=cur);

    }

}

void solve()

{

    int i;

    ss=bcnt=dindex=0;

    memset(dfn,0,sizeof(dfn));

    memset(iss,false,sizeof(iss));

    for(int i=1;i<=n;i++)

        if(!dfn[i])

            tarjan(i);

}

int main()

{

    //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(~scanf("%d",&n))

   {

       myv.clear();

       myv.resize(n+1);

       int m;

       scanf("%d",&m);

       for(int i=1;i<=m;i++)

       {

           int a,b;

           scanf("%d%d",&a,&b);

           myv[a].push_back(b);

       }

       solve();

       if(bcnt==1)

       {

           printf("1\n0\n");

           continue;

       }

       int ansa=0,ansb=0;

       memset(de1,0,sizeof(de1));

       memset(de2,0,sizeof(de2));

       for(int i=1;i<=n;i++)

       {

           for(int j=0;j<myv[i].size();j++)

           {

               int ne=myv[i][j];

               if(belong[i]!=belong[ne])

               {

                   de1[belong[ne]]++;//Èë¶È

                   de2[belong[i]]++; //³ö¶È

               }

           }

       }

       for(int i=1;i<=bcnt;i++)

       {

           if(!de1[i])

                ansa++;

           if(!de2[i])

                ansb++;

       }

       ansb=max(ansb,ansa);

       printf("%d\n",ansb);

   }

    return 0;

}