缩点+出入度 poj1236

题目链接：https://vjudge.net/contest/219056#problem/H

题意：先输入n，代表接下来有n个点，接下来n行，第i行里面的数（假设是）a，b...0（到0表示结束），表示点i和a，b有一条从i到a，b的有向边，现在叫我们求出两个答案，

第一个答案就是至少要选择几个点作为起点，才可以到达所有的点，

第二个答案就是至少要添加几条有向边才可以使得每次随便选择一个点都可以到达其他所有点（整个图就是一个强连通分量）。

思路：首先计算第一个答案：至少要几个点作为起点才可以到达其他所有点，如果是同一个强连通分量的点肯定可以相互到达，那我们就先缩点，得到一个有向无环图，那么我们的答案是不是就是缩点之后的图中入度为0的点，因为通过这些入度为0的点一定可以到达其他入度非0的点，那么我们的第一个答案就是缩点之后入度为0的点的个数。

第二个答案：至少要增加几条有向边才可以使这个图里面的点可以两两相互到达（只有一个强连通分量），首先在有向图里面如果没有入度为0并且也没有出度为0的点，那么这个图就是强连通的（应该不包括自己指向自己），在我们缩点之后，对于那些入度为0的点，我们想要到达，则必须要有一条有向边到达这些入度为0的点，假设入度为0的点的数量是in_um，对于出度为0,的点，我们必须至少连接一条有向边使得这个点可以到达其他点，假设出度为0的点的数量是out_num，那么第二个答案就是max(in_num,out_num)，因为我们可以增加有向边从出度为0的点指向入度为0的点，答案就是更大的数。

这里有个大坑就是如果缩点之后强连通分量数目为1，那么直接输出1 0就可以了，特例，我还是百度才知道的。

代码：

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<set>

#include<cstdio>

#include<string>

#include<deque>

using namespace std;

typedef long long LL;

#define eps 1e-8

#define INF 0x3f3f3f3f

#define maxn 105

vector<int>vec[maxn];

int n,m,k,t;

int vis[maxn];

int dfn[maxn],low[maxn],color[maxn],s[maxn],time,ans,top;

int in[maxn],out[maxn],flag[maxn][maxn];

void init()

{

    memset(vis,,sizeof(vis));

    memset(dfn,,sizeof(dfn));

    memset(in,,sizeof(in));

    memset(out,,sizeof(out));

    memset(flag,,sizeof(flag));

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

    {

        vec[i].clear();

    }

    time=top=ans=;

}

void DFS(int u)

{

    dfn[u]=low[u]=++time;

    s[top++]=u;

    vis[u]=true;

    for(int i=;i<vec[u].size();i++)

    {

        int v=vec[u][i];

        if(!dfn[v])

        {

            DFS(v);

            low[u]=min(low[u],low[v]);

        }

        else if(vis[v])

        low[u]=min(low[u],dfn[v]);

    }

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

    {

        ans++;

        int v;

        do{

            v=s[--top];

            vis[v]=false;

            color[v]=ans;//染色

        }while(u!=v);

    }

 }

void tarjan()

{

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

    {

        if(!dfn[i])

        DFS(i);

    }

}

void cal()//计算出入度

{

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

    {

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

        {

            int a=color[i];

            int b=color[vec[i][j]];

            if(a!=b)

            {

                if(flag[a][b]==)//标记a和b之间有没有有向边

                {

                    out[a]++;

                    in[b]++;

                    flag[a][b]++;

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        init();

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

        {

            int v;

            while(scanf("%d",&v)&&v)

            {

                vec[i].push_back(v);

            }

        }

        tarjan();

        if(ans==)//特例

        {

            printf("1\n0\n");

            continue;

         }

        cal();//计算出入度

        int in_num=,out_num=;//入度为0和出度为0的点的数目

        int sum1=,sum2=;

        for(int i=;i<=ans;i++)//注意ans，这是缩点之后点的数量，不要写成n了

        {

            if(!in[i])

            in_num++;

            if(!out[i])

            out_num++;

        }

        sum1=in_num;

        sum2=max(in_num,out_num);

        printf("%d\n%d\n",sum1,sum2);

    }

    return ;

}

巴特西

缩点+出入度 poj1236

最新文章

热门文章