强连通分量

等价性证明（强连通分量+缩点）

【问题描述】

在数学中，我们常常需要完成若⼲命题的等价性证明。

例如：有4个命题a,b,c,d，要证明他们是等价的，我们需要证明a<=>b，然后b<=>c，最后c<=>d。注意每次证明是双向的，因此⼀共

完成了6次推导。另⼀种证明⽅法是：证明a->b，然后b->c，接着c->d，最后d->a，只须4次证明。

现在你任务是证明n个命题全部等价，且你的朋友已经为你作出了m次推导（已知每次推导的内容），你⾄少还需做⼏次推导才能完成

整个证明。

【输⼊格式】

有T组数据，每组数据第⼀⾏为两个整数n和m，即命题数和已完成的推导个数（编号为1..n）。以下m⾏每⾏包含两个整数s1和

s2（1<=s1,s2<=n,s1!=s2)，表明已经证明了s1->s2。

【输出格式】

输出还需要做推导数的最⼩值。

【输⼊样例】

2

40

32

12

13

【输出样例】

4

2

【数据范围】

T<=100

1<=n<=20000

0<=m<=50000

分析：

1.分析可知，如给出A->B，那么需要找⼀系列推导推出B->A，即找⼀条路从B回到A，也就是找环，求强连通分量；

2.求出所有分量后，分量内部所有的都可以互相推出，不⽤考虑，只需考虑不同分量内的，所以缩点；

3.缩点后形成DAG图，要整个图变成强联通图，需要“消灭”⼊度或者出度为0的点，因此分别统计出度和⼊度为0的点，求⼤的⼀个答案

即可；

4.坑点：当整个图就是强联通图时，输出0；

代码：（菜鸡为了节约memt的时间⽤了结构体存时间，请忽视.....）

#include

#include

#include

usingnamespacestd;

constintmaxn=20005;

constintmaxm=50005;

intn,m,T,np=0,Time,last[maxn];

structedge{intto,pre;}E[maxm];

structdata{inttime,num;};

charc;

voidqkscanf(int&x)

{

for(c=getchar();c<'0'||c>'9';c=getchar());

for(x=0;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

}

voidaddedge(intu,intv)

{

E[++np]=(edge){v,last[u]};

last[u]=np;

}

intstk[maxn],top,dfs_clock,rd[maxn],cd[maxn],scc_cnt;

datadfn[maxn],low[maxn],belong[maxn];

voidDFS(inti)

{

dfn[i]=low[i]=(data){Time,++dfs_clock};

rd[i]=0,cd[i]=0;

stk[++top]=i;

for(intp=last[i];p;p=E[p].pre)

{

intj=E[p].to;

if(dfn[j].num&&dfn[j].time==Time)

{

if(!belong[j].num||belong[j].time!=Time)

{

low[i].num=min(low[i].num,dfn[j].num);

}

continue;

}

DFS(j);

low[i].num=min(low[i].num,low[j].num);

}

if(low[i].num==dfn[i].num)

{

scc_cnt++;

while(1)

{

intx=stk[top--];

belong[x]=(data){Time,scc_cnt};

if(x==i)break;

}

}

}

voidsuodian()

{

{

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

{

for(intp=last[i];p;p=E[p].pre)

{

intj=E[p].to;

if(belong[i].num!=belong[j].num)

{

cd[belong[i].num]++;

rd[belong[j].num]++;

}

}

}

}

voidinit()

{

memt(last,0,sizeof(last));

np=0;top=0;dfs_clock=0;scc_cnt=0;

}

intmain()

{

//freopen("","r",stdin);

qkscanf(T);

intu,v;

for(Time=1;Time<=T;Time++)

{

init();//初始化

qkscanf(n);qkscanf(m);

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

{

qkscanf(u);qkscanf(v);

addedge(u,v);

}

for(inti=1;i<=n;i++)if(!dfn[i].num||dfn[i].time!=Time)DFS(i);//求出连通分量

suodian();//缩点

inta=0,b=0;//统计出度、⼊度为0的点

for(inti=1;i<=scc_cnt;i++)

{

if(rd[i]==0)a++;

if(cd[i]==0)b++;

}

printf("%dn",scc_cnt==1?0:max(a,b));

}

return0;

}