社区讨论

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 条回复,欢迎继续交流。

正在加载回复...