Submission #68020

ソースコード

?
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
#define rep(i, x, n) for (int i = (x); i < (n); i++)
#define reps(i, x, n) for (int i = (x); i <= (n); i++)
#define lol long long
#define SUM(n) ((n) + 1) * (n) / 2 // 1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed << setprecision(x + 1) //小数点桁数を指定する
#define abs(x, y) max(x, y) - min(x, y)
#define all(v) v.begin(), v.end()
#define UPDigit(a, b) (a + b - 1) / b //小数点切り上げ
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = int(1e9) + 7;
using namespace std;
using pii = pair<int, int>;
typedef vector<int> vit;
//八方向を見るのに使うと便利(楽)
const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
vector<int> edge[10005], rev_edge[10005];
vector<int> scc(10005, INF); // 強連結成分の番号
stack<int> pass_order;
vector<bool> pass_flag;
void dfs(int now){
pass_flag[now] = true;
rep(i, 0, edge[now].size()){
int next = edge[now][i];
if(!pass_flag[next]){
dfs(next);
}
}
// 順番をメモ
pass_order.emplace(now);
//cout << now << " ";
return;
}
void rev_dfs(int now, int cnt){
pass_flag[now] = true;
scc[now] = cnt;
rep(i, 0, rev_edge[now].size()){
int next = rev_edge[now][i];
if(!pass_flag[next]){
rev_dfs(next, cnt);
}
}
return;
}
signed main(void) {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
// 入力
int n, m;
cin >> n >> m;
int s, t;
reps(i, 1, m){
cin >> s >> t;
edge[s].emplace_back(t);
rev_edge[t].emplace_back(s);
}
// 強連結成分分解
// 普通にDFS
pass_flag.assign(n + 5, false);
rep(i, 0, n){
if(!pass_flag[i]){
dfs(i);
}
}
// 辺を逆にしてDFS
pass_flag.assign(n + 5, false);
int cnt = 0; // 強連結成分の個数
while(!pass_order.empty()){
int elm = pass_order.top();
pass_order.pop();
if(!pass_flag[elm]){
rev_dfs(elm, cnt);
cnt ++;
}
}
// 強連結成分が1つしかない
if(cnt == 1){
cout << "0\n";
return 0;
}
/*rep(i, 0, n){
cout << scc[i] << ' ';
}
cout << '\n';*/
// ノードを圧縮
vector<int> new_edge[cnt + 5];
vector<int> edge_cnt(cnt + 5, 0);
rep(i, 0, n){
for(auto x : edge[i]){
// 同じ強連結成分でない かつ 新たな辺
if(scc[i] != scc[x] && find(all(new_edge[scc[i]]), scc[x]) == new_edge[scc[i]].end()){
// cout << scc[i] << " " << scc[x] << " " << i << " " << x << '\n';
new_edge[scc[i]].emplace_back(scc[x]);
edge_cnt[scc[x]] ++;
}
}
}
/*rep(i, 0, cnt){
cout << i << '\n';
for(auto x : new_edge[i]){
cout << x << " ";
}
cout << '\n';
} */
int ans1, ans2;
ans1 = ans2 = 0;
// 入次数0のノードを数える
rep(i, 0, cnt){
if(!new_edge[i].size()){
ans1 ++;
}
}
// 出次数0のノードを数える
rep(i, 0, cnt){
if(!edge_cnt[i]){
ans2 ++;
}
}
cout << max(ans1, ans2) << '\n';
return 0;
}

ステータス

項目 データ
問題 0964 - 道路網改修
ユーザー名 NASSUN_ei1906
投稿日時 2021-08-06 11:35:09
言語 C++17
状態 Accepted
得点 14
ソースコード長 3266 Byte
最大実行時間 46 ms
最大メモリ使用量 3444 KB

セット

セット 得点 Cases
1 ALL 14 / 14 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 20 ms 1116 KB
1
in2.txt AC 18 ms 1060 KB
1
in3.txt AC 18 ms 1164 KB
1
in4.txt AC 23 ms 1172 KB
1
in5.txt AC 18 ms 1132 KB
1
in6.txt AC 17 ms 1476 KB
1
in7.txt AC 27 ms 2540 KB
1
in8.txt AC 25 ms 1564 KB
1
in9.txt AC 39 ms 2888 KB
1
in10.txt AC 36 ms 1968 KB
1
in11.txt AC 25 ms 1624 KB
1
in12.txt AC 26 ms 2016 KB
1
in13.txt AC 23 ms 968 KB
1
in14.txt AC 40 ms 3104 KB
1
in15.txt AC 39 ms 3444 KB
1
in16.txt AC 46 ms 3008 KB
1
in17.txt AC 38 ms 3100 KB
1
in18.txt AC 23 ms 1140 KB
1
in19.txt AC 20 ms 1100 KB
1
in20.txt AC 30 ms 1788 KB
1
in21.txt AC 25 ms 1160 KB
1
in22.txt AC 19 ms 1300 KB
1
in23.txt AC 21 ms 1368 KB
1
in24.txt AC 25 ms 1476 KB
1
in25.txt AC 24 ms 1504 KB
1
in26.txt AC 23 ms 1584 KB
1
in27.txt AC 31 ms 1716 KB
1
in28.txt AC 26 ms 2076 KB
1
in29.txt AC 44 ms 2704 KB
1
in30.txt AC 38 ms 3168 KB
1