「Luogu P2341」[HAOI2006]受欢迎的牛

发表于 |
字数统计: 352 | 阅读时长 ≈ 2

给定一个有向图，找出与其他点均可达的点的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct edge{
    ll to,prev;
};
edge ed[150001],scc[150001];
ll sccno,tot,num,top,cnt,nc,ec,ans;
ll last[150001],sccLast[150001],dfn[150001],low[150001],ins[150001],belong[150001];
ll from[150001],to[150001],size[150001],out[150001];
stack<ll>st;
inline void addEdge(ll from,ll to)
{
    ed[++tot].to=to;
    ed[tot].prev=last[from];
    last[from]=tot;
}
inline void addSCC(ll from,ll to)
{
    scc[++tot].to=to;
    scc[tot].prev=sccLast[from];
    sccLast[from]=tot;
}
inline void tarjan(ll node)
{
    dfn[node]=low[node]=++num;
    st.push(node),ins[node]=1;
    ll flag=0,to;
    for(register int i=last[node];i;i=ed[i].prev)
    {
        to=ed[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[node]=min(low[node],low[to]);
        }
        else
        {
            if(ins[to])
            {
                low[node]=min(low[node],dfn[to]);
            }
        }
    }
    if(dfn[node]==low[node])
    {
        cnt++;
        ll nd;
        do
        {
            nd=st.top(),st.pop();
            ins[nd]=0;
            belong[nd]=cnt;
            size[cnt]++;
        }
        while(node!=nd);
    }
}
inline void mergePoint()
{
    tot=0;
    for(register int i=0;i<ec;i++)
    {
        if(belong[from[i]]!=belong[to[i]])
        {
            addSCC(belong[from[i]],belong[to[i]]);
            out[belong[from[i]]]++;
        }
    }
}
int main()
{
    cin>>nc>>ec;
    for(register int i=0;i<ec;i++)
    {
        cin>>from[i]>>to[i];
        addEdge(from[i],to[i]);
    }
    for(register int i=1;i<=nc;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    mergePoint();
    for(register int i=1;i<=cnt;i++)
    {
    	if(!out[i])
    	{
    		ans++;
    		sccno=i;
        }
    }
    if(ans!=1)
    {
    	cout<<0;
    }
    else
    {
        cout<<size[sccno];
    }
}