LA4287--tarjan

2018-06-18 00:06:41来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目大意:

      在数学中,我们常常需要完成若干个命题的等价性证明。比如,有4个命题a,b,c,d,我们证明a↔b,然后b↔c,最后c↔d。注意每次证明都是双向的,因此一共完成了6次推导。另一种方法是a→b,然后b→c,接着c→d,最后d→a,只需4次。现在你的任务是证明n个命题全部等价,且你的朋友已经为你做出了m次推导(已知每次推导的内容),你至少还需要做几次推导才能完成整个证明?

先tarjan一遍求出强连通分量,缩点,统计每个点的出入度。设有a个节点入读为0,b个节点出度为0,则答案就是max(a,b)。

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string.h>
using namespace std;
vector<int>g[20001];
int n,m,t,i,j,x,y,dfn[20001],dfs_clock,low[20001],in0[20001],out0[20001],c[20001],a,b,l,f[20001],cnt;
void dfs(int u){
    dfn[u]=low[u]=++dfs_clock;
    c[++l]=u;
    for(int i=0;i<g[u].size();++i)
    if(!dfn[g[u][i]]){
        dfs(g[u][i]);
        low[u]=min(low[u],low[g[u][i]]);
    }else if(!f[g[u][i]])low[u]=min(low[u],dfn[g[u][i]]);
    if(low[u]==dfn[u]){
        cnt++;
        while(c[l]!=u)f[c[l--]]=cnt;
        f[c[l--]]=cnt;
    }
}
int main()
{
    scanf("%d",&t);
    for(int u=0;u<t;++u){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;++i)g[i].clear();
        for(i=1;i<=m;++i){
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
        }
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(in0,0,sizeof(in0));
        memset(out0,0,sizeof(out0));
        memset(f,0,sizeof(f));
        memset(c,0,sizeof(c));
        a=0;b=0;l=0;cnt=0;dfs_clock=0;
        for(i=1;i<=n;++i)if(!dfn[i])dfs(i);
        for(i=1;i<=n;++i)
        for(j=0;j<g[i].size();++j)
        if(f[g[i][j]]!=f[i]){
            in0[f[g[i][j]]]++;
            out0[f[i]]++;
        }
        for(i=1;i<=cnt;++i){
            if(!in0[i])a++;
            if(!out0[i])b++;
        }
        if(cnt==1)printf("0\n");else printf("%d\n",max(a,b));
    }
    return 0;
}
LA4287

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:ESP8266开发课堂之 - 建立一个新项目

下一篇:返回“字符串常量的指针”和“返回数组名”的区别