1. 题目

传送门= ̄ω ̄=

2. 题解

强联通分量,缩点模板题。
第一个问题的答案是缩点以后入度为0的点的个数
第二个问题的答案是缩点以后入度为0的点的个数和出度为0的点的个数中较大的那个
如果只有1个强联通分量,那么第二问答案为0,需要特判

至于证明的话,可以看这个,我懒得写了:

—给定一个有向图,求:

1) 至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点

2) 至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点

— 顶点数<= 100 解题思路: 1. 求出所有强连通分量 2. 每个强连通分量缩成一点,则形成一个有向无环图DAG。 3. DAG上面有多少个入度为0的顶点,问题1的答案就是多少 在DAG上要加几条边,才能使得DAG变成强连通的,问题2的答案就是多少 加边的方法: 要为每个入度为0的点添加入边,为每个出度为0的点添加出边 假定有 n 个入度为0的点,m个出度为0的点,如何加边? 把所有入度为0的点编号 0,1,2,3,4 ….N -1 每次为一个编号为i的入度0点可达的出度0点,添加一条出边,连到编号为(i+1)%N 的那个出度0点, 这需要加n条边 若 m <= n,则 加了这n条边后,已经没有入度0点,则问题解决,一共加了n条边 若 m > n,则还有m-n个入度0点,则从这些点以外任取一点,和这些点都连上边,即可,这还需加m-n条边。
所以,max(m,n)就是第二个问题的解
此外:当只有一个强连通分支的时候,就是缩点后只有一个点,虽然入度出度为0的都有一个,但是实际上不需要增加清单的项了,所以答案是1,0;

代码(kosaraju):

#include <cstdio>
#include <cctype>
#include <cstring>
#include <stack>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,head[2][105],nxt[2][10005],to[2][10005],size[2],cnt,pos[105],ans1,ans2;
bool book[105],book2[105];
stack<int> st;
void push(int g,int a,int b)
{
    to[g][size[g]]=b,nxt[g][size[g]]=head[g][a],head[g][a]=size[g]++;
}
void init(int u)
{
    book[u]=1;
    for(int i=head[0][u];i!=-1;i=nxt[0][i])if(!book[to[0][i]])init(to[0][i]);
    st.push(u);
}
void dfs(int u)
{
    book[u]=1,pos[u]=cnt;
    for(int i=head[1][u];i!=-1;i=nxt[1][i])if(!book[to[1][i]])dfs(to[1][i]);
}
int main()
{
    IN(n),memset(head,-1,sizeof(head));
    for(int i=1,j;i<=n;i++)while(IN(j),j)push(0,i,j),push(1,j,i);
    for(int i=1;i<=n;i++)if(!book[i])init(i);
    memset(book,0,sizeof(book));
    while(!st.empty())
    {
        int u=st.top();st.pop();
        if(!book[u])cnt++,dfs(u);
    }
    if(cnt==1){printf("1\n0\n");return 0;}
    memset(book,0,sizeof(book));
    for(int i=1;i<=n;i++)
        for(int j=head[0][i];j!=-1;j=nxt[0][j])
            if(pos[to[0][j]]!=pos[i])
                book[pos[to[0][j]]]=1,book2[pos[i]]=1;
    for(int i=1;i<=cnt;i++){if(!book[i])ans1++;if(!book2[i])ans2++;}
    printf("%d\n%d\n",ans1,max(ans1,ans2));
    return 0;
} 

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *