wuwendongxi

8250

JayZ

leimingze
WuHeng_akNOIP

Coisi
KkkkkkkkkKK

ArkhamKnight

ssuunn

CZ-7
CLOVER

wuwendongxi
16小时前

https://www.acwing.com/community/content/618950/

https://www.acwing.com/problem/content/description/367/

7行tarjan代码戳原帖

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2003;
bool lk[maxn][maxn],tag[maxn];
struct node{int next,to;}e[4000003];
void tarjan(int x,int pre){//tarjan缩点
dfn[x]=low[x]=++cnt;sta[++idx]=x;
if(!dfn[v]) tarjan(v,x),low[x]=min(low[x],low[v]);
else low[x]=min(low[x],dfn[v]);
if(low[x]==dfn[x]) for(++num;sta[idx+1]!=x;--idx) bel[sta[idx]]=num,siz[num]++;
}
bool dfs(int x,int col){//2分图染色判奇环
vis[x]=col;
if(bel[v]==bel[x])
if(!vis[v]) return dfs(v,3-col);
else if(vis[v]==col) return 1;
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m),n||m){
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j) lk[i][j]=lk[j][i]=0;
}idx=num=ans=0,cnt=1;
for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),lk[u][v]=lk[v][u]=1;
cnt=0;for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
for(int i=1,tmp;i<=n;++i) if(!tag[bel[i]]) tag[bel[i]]=1,tmp=dfs(i,1),ans+=tmp*siz[bel[i]];
cout<<n-ans<<'\n';
}
return 0;
}


https://www.acwing.com/problem/content/description/367/

tarjan找点双连同分量如下：

void tarjan(int x,int pre){
dfn[x]=low[x]=++cnt;sta[++idx]=x;
if(!dfn[v]) tarjan(v,i),low[x]=min(low[x],low[v]);
else low[x]=min(low[x],dfn[v]);
if(low[x]==dfn[x]) for(++num;sta[idx+1]!=x;--idx) bel[sta[idx]]=num,siz[num]++;
}


wuwendongxi
10个月前

wuwendongxi
10个月前

wuwendongxi
10个月前

wuwendongxi
10个月前

wuwendongxi
2020-09-08 07:48