社区讨论

90分求助orz

P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi6wdg0y
此快照首次捕获于
2025/11/20 11:54
4 个月前
此快照最后确认于
2025/11/20 11:54
4 个月前
查看原帖
CPP
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#define ll long long
#define maxn 20000+10 
#define maxm 50000+10
#define inf 0x7fffffff
using namespace std;

bool vis[maxn];
int n,m,num,tot,indx,ans,top;
int dfn[maxn],low[maxn],fir[maxn],sta[maxn];
int u[maxn],v[maxn],color[maxn],val[maxn],deg[maxn];

struct qwq
{
    int to,nxt;
}e[maxm];

int read()
{
    int xx=0,kk=1;char ch=' ';
    while(!isdigit(ch)){ch=getchar();if(ch=='-')kk=-1;}
    while(isdigit(ch)){xx=xx*10+ch-'0';ch=getchar();}
    return kk*xx;
}

void addedge(int u,int v)
{
    e[++num].to=v;
    e[num].nxt=fir[u];
    fir[u]=num;
}

void tarjan(int x)
{
    sta[++top]=x;
    vis[x]=true;
    dfn[x]=low[x]=++indx;
    for(int i=fir[x];i;i=e[i].nxt)
    {
        int tx=e[i].to;
        if(!dfn[tx])
        {
        	tarjan(tx);
        	low[x]=min(low[x],low[tx]);
        }
        else if(vis[tx]) low[x]=min(low[x],dfn[tx]);
    }
    if(dfn[x]==low[x])
    {
        tot++;
        while(sta[top+1]!=x)
        {
            val[tot]++;
            color[sta[top]]=tot;
            vis[sta[top--]]=false;
        }
    }
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)
        u[i]=read(),v[i]=read(),addedge(u[i],v[i]);
    for(int i=1;i<=n;++i)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=m;++i)
        if(color[u[i]]!=color[v[i]])
            deg[color[u[i]]]++;
    for(int i=1;i<=tot;++i)	
    {
        if(!deg[i]&&!ans){ans=val[i];continue;} 
        if(!deg[i]&&ans){ans=0;break;} 
    }
    printf("%d",ans);
    return 0;
}
有两个点expected 5,read 0 orz

回复

0 条回复,欢迎继续交流。

正在加载回复...