社区讨论
91分 第10个点WA 求救qwq
P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 4已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi6lowuw
- 此快照首次捕获于
- 2025/11/20 06:55 4 个月前
- 此快照最后确认于
- 2025/11/20 06:55 4 个月前
第十个点 read 0,ecpected 10000
贴上代码
CPP#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
const int MAXN = 500005;
inline void read(int &x)
{
char ch = getchar(),c = ch;x = 0;
while(ch < '0' || ch > '9') c = ch,ch = getchar();
while(ch <= '9' && ch >= '0') x = (x<<1)+(x<<3)+ch-'0',ch = getchar();
if(c == '-') x = -x;
}
int head[MAXN],dfn[MAXN],low[MAXN];
int belong[MAXN],sum[MAXN],out[MAXN];
int cnt,dfn_cnt,part,n,m,f,t,ans,flag;
inline int Min(int a,int b)
{return a<b?a:b;}
struct Edge
{
int f,t,nxt;
}e[MAXN];
inline void insert(int f,int t)
{
e[++cnt].f = f,e[cnt].t = t;
e[cnt].nxt = head[f],head[f] = cnt;
}
std::stack <int> s;
void Tarjan(int u)
{
s.push(u);
dfn[u] = low[u] = ++ dfn_cnt;
for(int i = head[u];i != -1;i = e[i].nxt)
{
int v = e[i].t;
if(!dfn[v]){
Tarjan(v);
low[v] = Min(low[u],low[v]);
}
else if(!belong[v])
low[u] = Min(low[u],dfn[v]);
}
if(dfn[u] == low[u])
{
++ part;
while(!s.empty())
{
int x = s.top();
s.pop();
belong[x] = part;
sum[part] ++;
if(x == u) break;
}
}
}
int main()
{
memset(head,-1,sizeof(head));
read(n),read(m);
for(int i = 1;i <= m;++ i)
{
read(f),read(t);
insert(f,t);
}
for(int i = 1;i <= n;++ i)
if(!dfn[i])
Tarjan(i);
for(int i = 1;i <= m;++ i)
if(belong[e[i].f] != belong[e[i].t])
out[belong[e[i].f]] ++;
for(int i = 1;i <= part;++ i)
{
if(!flag && !out[i]){
flag = 1;
ans = sum[i];
}
else if(flag && !out[i]){
ans = 0;
break;
}
}
printf("%d\n",ans);
return 0;
}
看了好几遍感觉并没啥错...并不知道问题在哪QAQ又不给数据下载
回复
共 6 条回复,欢迎继续交流。
正在加载回复...