洛谷P2341：https://www.luogu.org/problemnew/show/P2341
前言
这题看错题目 足足花了将近5小时提交了15次 在一位dalao的提醒下才AC了
记得要看清题意啊！
思路
可以成为明星的牛是图中唯一的出度为0的强连通分量中的所有牛
因为如果有两个或以上的话 他们之间无法互相爱慕
即可把所有互相爱慕的牛用Tarjan缩点
判断如果出度为0的强连通分量只有一个 就输出这个强连通分量中的牛数
如果有两个或以上即无解
代码
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 10010
int n,m,cnt,num,col,top,ans,pd;
int dfn[maxn],low[maxn],de[maxn],cow[maxn],f[maxn],st[maxn],h[maxn],co[maxn];
bool vis[maxn];
struct Edge
{
int to;
int next;
}e[maxn*
5];
void add(
int x,
int y)
{
e[++cnt].to=
y;
e[cnt].next=
h[x];
h[x]=
cnt;
}
void Tarjan(
int u)
{
dfn[u]=low[u]=++
num;
st[++top]=u;
//入栈
vis[u]=
1;
//判断是否在栈中
for(
int i=h[u];i;i=
e[i].next)
{
int v=
e[i].to;
if(!
dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
//low表示u与其子孙到达的最小编号
}
else
if(vis[v])
//判断v是否在栈中
low[u]=
min(low[u],dfn[v]);
//可以改成 min(low[u],low[v])
//因为此时v的low和dfn还未修改
}
if(dfn[u]==
low[u])
{
co[u]=++col;
//属于第col个强连通分量
++cow[col];
//计算第col个强连通分量中有几头牛
while(st[top]!=
u)
{
++
cow[col];
co[st[top]]=
col;
vis[st[top--]]=
0;
}
--
top;
}
}
int main()
{
scanf("%d%d",&n,&
m);
for(
int i=
1;i<=m;i++
)
{
int x,y;
scanf("%d%d",&x,&
y);
add(x,y);
}
for(
int i=
1;i<=n;i++
)
if(!dfn[i]) Tarjan(i);
//缩点
for(
int i=
1;i<=n;i++)
//统计出度
for(
int j=h[i];j;j=
e[j].next)
if(co[i]!=co[e[j].to])
//如果不是同一个强连通分量
de[co[i]]++
;
for(
int i=
1;i<=col;i++
)
if(!
de[i])
{
ans=cow[i];
//出度为0 说明这头牛是被所有牛喜欢
pd++
;
}
if(pd==
1)
printf("%d",ans);
else
printf("0");
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9688405.html
