對於每個強聯通分量,這些牛一定都互相喜歡,所以縮點(我也不知道怎麼想到的)

接下來就是統計答案,最後縮成了一個DAG圖,如果這個點是明星的話,其他每個點一定直接或間接的鏈接這個點

也就是說其他點一定有出度,把關係傳遞給其他點了,如果某個點沒有出度,那麼這個點沒有傳遞出他們的愛慕關係,

如果存在多個這樣的點的話自然每個點都不會傳遞出他們的愛慕關係,也就不會有某個點成為明星了

所以如果出度為0得點只有一個,那麼答案就是它的點數,不然答案為0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
int n,m,tim,top;
struct node{
int u,v,nxt;
}e[maxm*],e2[maxm*];
int head[maxn],cnt,head2[maxn],cnt2;
void add(int u,int v){
e[++cnt].u=u;e[cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int stac[maxn],vis[maxn],dfn[maxn],low[maxn],out[maxn],p[maxn],sd[maxn];
void tarjan(int x){
low[x]=dfn[x]=++tim;
stac[++top]=x;vis[x]=;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].v;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y])low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x]){
int y;
while(y=stac[top--]){
sd[y]=x;
vis[y]=;
if(x==y)break;
p[x]+=p[y];
}
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)p[i]=;
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=;i<=m;i++){
int x=sd[e[i].u],y=sd[e[i].v];
if(x!=y){
e2[++cnt2].u=x;
e2[cnt2].v=y;
e2[cnt2].nxt=head2[x];
out[x]++;
}
}
int tot=,ans=;
for(int i=;i<=n;i++)if(sd[i]==i && out[i]==)tot++,ans=i;
if(tot==)printf("%d",p[ans]);
else printf("");
}
05-08 15:48