「Luogu P2002」消息扩散

发表于 |
字数统计: 359 | 阅读时长 ≈ 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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct edge{
    ll to,prev;
};
edge ed[500001],scc[500001];
ll test,tot,num,top,cnt,nc,ec,ans;
ll last[500001],sccLast[500001],dfn[500001],low[500001],ins[500001],belong[500001];
ll from[500001],to[500001],size[500001],in[500001];
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]]);
            in[belong[to[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(!in[i])
    	{
    		ans++;
        }
    }
    cout<<ans<<endl;
}