社区讨论
85分是哪里有问题呀qwq
P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6vw916
- 此快照首次捕获于
- 2025/11/20 11:41 4 个月前
- 此快照最后确认于
- 2025/11/20 11:41 4 个月前
CPP
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#define ll long long
#define maxn 10000+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=0;break;}
if(!deg[i]&&!ans) ans=val[i];
}
printf("%d",ans);
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...