MnZn Tarjan板子题求助
查看原帖
MnZn Tarjan板子题求助
450861
QcpyWcpyQ楼主2022/3/27 15:34

rt,52pts,WA了六个点 代码如下:

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,m,head[N],tot;
struct Edge{
    int to,nxt;
}edge[N];
int dfn[N],low[N],stk[N],top;
bool ins[N];
int cnt,idx,siz[N],scc[N];

inline int read(){
	int s=0,f=1;char ch=getchar();
	while(ch<'0' or ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' and ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}

inline void write(int num){
	if(num<0)putchar('-');
	if(num>9)write(num/10);
	putchar(num%10+48);
}

inline void add(int u,int v){
    edge[++tot].to=v;
    edge[cnt].nxt=head[u];
    head[u]=tot;
}

inline void tarjan(int u){
    low[u]=dfn[u]=++cnt;
    ins[stk[++top]=u]=true;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(ins[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int v;idx++;
        do{
            v=stk[top--];
            scc[v]=idx;
            siz[idx]++;
        }while(v!=u);
    }
}

int main(){
    n=read(),m=read();
    for(int i=1,u,v;i<=m;i++){
        u=read(),v=read();
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
    int ans=0;
    for(int i=1;i<=idx;i++)
        ans+=siz[i]>1;
    write(ans);
    return 0;
}
2022/3/27 15:34
加载中...