Problem
苏塞克王国是世界上创新技术的领先国家，在王国中有n个城市，标记为1到n。
由于小K的研究，我们最终能过在两个城市之间建立传输管道，一个传输管道能单向连接两个城市，即，一个从城市x到城市y的传输管道不能被用于从城市y传输到城市x。在每个城市之间的运输系统已经建立完善，因此，如果从城市x到城市y的管道和从城市y到城市z的管道都被已经被建立，人们能够立即从x到z。
小K也研究了国家政治，他认为在这m对城市(ai, bi) (1 ≤ i ≤ m)之间的传输尤其重要。他正在计划为每个重要城市对(ai, bi)建立传输管道，通过使用一个或多个传输管道，我们可以从城市ai到城市bi（但不需要从城市bi到城市ai）。我们要找出必须建立的传输管道的最小数。至今，还没有传输管道被建立，在每个城市之间也没有其他有效的传输方式。
Solution
一个弱连通图，如果不包含强连通分量，可以按照拓扑排序连边，则对答案的贡献为n-1，如果包含强连通分量，拓扑以后还有环，对答案的贡献是n，因此先用Tarjan缩点，然后并查集合并弱连通图求个数，再把包含强连通分量的弱连通图个数求出来，答案是点数-(弱连通图个数-含有强连通分量的弱连通图个数)。
Code
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
104
105
106
107
108
109
110
111
| #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=100020;
const int MAXM=100020;
int n,m,idx,cnt,mm;
int g[MAXN],dfn[MAXN],low[MAXN],p2p[MAXN];
bool instack[MAXN];
stack<int>s;
vector<int>belong[MAXN];
struct E{
int u,v,nex;
bool operator<(const E x)const{
if(u==x.u) return v<x.v;
return u<x.u;
}
bool operator==(const E x)const{
return u==x.u&&v==x.v&&nex==x.nex;
}
}e[MAXM];
void Tarjan(int u){
dfn[u]=low[u]=++idx;
s.push(u);
instack[u]=true;
for(int i=g[u];i>0;i=e[i].nex){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
++cnt;
int cur;
do{
cur=s.top();s.pop();
instack[cur]=false;
belong[cnt].push_back(cur);
p2p[cur]=cnt;
}while(cur!=u);
}
}
int f[100020];
bool ltk[100020];
int ltk_num;
bool havltk[100020];
int havltk_num;
int find(int x){
return f[x]==0?x:f[x]=find(f[x]);
}
int main(){
io_opt;
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
e[i]=(E){x,y,g[x]};g[x]=i;
}
for(int i=1;i<=n;i++){
if(!dfn[i]) Tarjan(i);
}
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
if(!p2p[u]||!p2p[v]||p2p[u]==p2p[v]){
e[i].u=e[i].v=1000000;
e[i].nex=1000000;
}
else{
e[i].u=p2p[u];
e[i].v=p2p[v];
e[i].nex=0;
}
}
sort(e+1,e+1+m);
mm=unique(e+1,e+1+m)-(e+1);
while(e[mm].nex==1000000) mm--;
memset(g,0,sizeof(g));
for(int i=1;i<=mm;i++){
e[i].nex=g[e[i].u];
g[e[i].u]=i;
int u=find(e[i].u),v=find(e[i].v);
if(u!=v){
f[u]=v;
}
}
for(int i=1;i<=cnt;i++){
int ff=find(i);
ltk[ff]=true;
if(belong[i].size()>1){
havltk[ff]=true;
}
}
for(int i=1;i<=cnt;i++){
if(ltk[i]) ltk_num++;
if(havltk[i]) havltk_num++;
}
cout<<n-(ltk_num-havltk_num)<<endl;
return 0;
}
|