LA4287--tarjan，la4287代換
題目大意：
在數學中，我們常常需要完成若干個命題的等價性證明。比如，有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
