您的位置: 首页  >  IT文章  >  Pku1236 Network of Schools

Pku1236 Network of Schools

分类: IT文章 • 2022-06-18 21:38:44

n个学校构成一个有向图，通过m条边连接，一：问至少向图中多少个学校投放软件，可以使得所有学校直接或者间接的通过边（假设存在边(u,v)，则向u投放v可以得到，而向v投放u不能通过v直接得到）得到软件（假设每次投放的软件无穷多）。二：问至少添加多少条有向边，可以使得只用向任意一个学校投放软件后，别的学校都能得到软件
输入
第一行给出数字N，N<=100
接下来N行给出每个点的连通情况，每行给出一些数字代表第i个学校与哪些学校相连接，每行输入以0代表结束
输出
如题

Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
1
2

其实就是强连通缩点，
问一是统计缩点后有多少分量入度为0，
问二是指至少添加多少边使得图强连通。
然后统计入度为0的点的个数in和出度为0的点的个数ou，
则问一输出in，问二如果整个图强连通则输出0，否则输出max{in,ou}。
为什么是max{in,ou}？
因为要使得图强连通，则必定每个点的出度以及入度都不为0

#include<algorithm>
#include<cstdio>
using namespace std;
int son[10100],n,m,ans1,group,low[10100],dfn[10100],st[10100],tot,now[10100],used[11000],popp[11000],topp[11000],a[11000],b[11000],ans2;
void add(int x,int y)
{
    tot++;
    now[tot]=son[x];
    son[x]=tot;
}
int top,sum,cnt,totle;
void dfs(int deep)
{
    st[++top]=deep;
    dfn[deep]=++cnt;
    low[deep]=dfn[deep];
    int nnow=top;
    for(int i=son[deep];i;i=now[i])
        if(!used[b[i]])
        {
            if(!dfn[b[i]])
                dfs(b[i]);
            low[deep]=min(low[b[i]],low[deep]);
        }
    if(dfn[deep]==low[deep])
    {
        totle++;
        for(int i=nnow;i<=top;i++)
            used[st[i]]=totle;
        top=nnow-1;
    }
}
int main()
{
    int v,k=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v);
        while(v)
        {
            add(i,v);
            a[++k]=i;
			b[k]=v;
            scanf("%d",&v);
        }
    }
    for(int i=1;i<=n;i++)
        if(!used[i])dfs(i);
    for(int i=1;i<=k;i++)
        if(used[a[i]]!=used[b[i]])
		   ++popp[used[a[i]]],
		   topp[used[b[i]]]++;
    for(int i=1;i<=totle;i++)
    {
        if(topp[i]==0)
		   ans1++;
        if(popp[i]==0)
		   ans2++;
    }
    ans2=max(ans1,ans2);
    if(totle==1)
	   ans2=0;
    printf("%d
%d",ans1,ans2);
}

　　

#include<cstdio>
#include<algorithm>
using namespace std;
int s[10010],st[110],hea[110],en[110],in[110],dfn[110],low[110],cd[110],rd[110],num,cnt,top,n,m;
void tarjan(int x)
{
    low[x]=dfn[x]=++num;
    st[++top]=x;
    for(int i=hea[x];i<en[x];i++)
    {
        int y=s[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(!in[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        cnt++;
        while(top&&st[top]!=x)in[st[top--]]=cnt;
        in[st[top--]]=cnt;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        en[i]=hea[i]=en[i-1];
        while(scanf("%d",s+en[i])&&s[en[i]])en[i]++;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=hea[i];j<en[i];j++)
            if(in[i]!=in[s[j]])
                cd[in[i]]++,rd[in[s[j]]]++;
    int c=0,r=0;
    for(int i=1;i<=cnt;i++)
    {
        if(!cd[i])c++;
        if(!rd[i])r++;
    }
    printf("%d
",r);
    if(cnt==1)puts("0");
    else printf("%d
",max(c,r));
    return 0;
}

　　

相关推荐