Submission #42432

ソースコード

?
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int SIZE = 10005;
int n,m;
int num[SIZE]={};
bool flag[SIZE]={};
int parent[SIZE];
set<int> st;
set<P> st2;
vector<int> order[SIZE], rev[SIZE];
int vec[SIZE][2]={};
priority_queue<P, vector<P> > que;
//Kyo
int dfs1(int i, int index);
void dfs2(int i);
//Union_find
void init();
void unite(int x, int y);
int find(int x);
bool same(int x, int y);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
init();
cin >> n >> m;
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
order[a].push_back(b);
rev[b].push_back(a);
}
int index = 1;
for(int i=0;i<n;i++){
if(num[i] == 0){
index = dfs1(i, index)+1;
}
}
/*
for(int i=0;i<n;i++){
cout << i << " = " << num[i] << endl;
}
*/
int count = 0;
while(!que.empty() && st.size() < n){
P p = que.top(); que.pop();
int pos = p.second;
int cost = p.first;
if(st.find(pos) != st.end()) continue;
count++;
dfs2(pos);
}
/*
for(int i=0;i<n;i++){
cout << i << " = root = " << find(i) << endl;
}
*/
if(count == 1) cout << 0 << endl;
else {
int in=0,out=0;
st.clear();
for(int i=0;i<n;i++){
int found = find(i);
if(st.find(found) != st.end()) continue;
st.insert(found);
if(vec[found][0] == 0) in++;
if(vec[found][1] == 0) out++;
}
cout << max(in, out) << endl;
}
return 0;
}
int dfs1(int i, int index)
{
if(flag[i]) return 0;//なくてもいい
flag[i] = true;
for(int j=0;j<order[i].size();j++){
int next = order[i][j];
if(!flag[next]){
index = dfs1(next, index)+1;
}
}
num[i] = index;
que.push(P(index, i));
return(index);
}
void dfs2(int i)
{
if(st.find(i) != st.end()) return;
st.insert(i);
for(int j=0;j<rev[i].size();j++){
int next = rev[i][j];
P a = P(min(i, next), max(i, next));
if(st.find(next) == st.end()){
unite(i, next);
dfs2(next);
} else if(!same(i, next) && st2.find(a) == st2.end()){
vec[find(i)][1]++;
vec[find(next)][0]++;
st2.insert(a);
}
}
return;
}
void init()
{
for(int i=0;i<SIZE;i++) parent[i] = i;
return;
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if(x == y) return;
parent[y] = x;
return;
}
int find(int x)
{
if(x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
bool same(int x, int y)
{
return( find(x) == find(y));
}

ステータス

項目 データ
問題 0964 - 道路網改修
ユーザー名 ei1612
投稿日時 2018-08-31 11:15:09
言語 C++11
状態 Accepted
得点 14
ソースコード長 2644 Byte
最大実行時間 87 ms
最大メモリ使用量 7812 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 24 ms 988 KB
1
in2.txt AC 18 ms 1148 KB
1
in3.txt AC 21 ms 1128 KB
1
in4.txt AC 24 ms 1156 KB
1
in5.txt AC 24 ms 1104 KB
1
in6.txt AC 24 ms 1820 KB
1
in7.txt AC 33 ms 3616 KB
1
in8.txt AC 26 ms 2080 KB
1
in9.txt AC 52 ms 3228 KB
1
in10.txt AC 42 ms 2600 KB
1
in11.txt AC 33 ms 2456 KB
1
in12.txt AC 28 ms 2924 KB
1
in13.txt AC 19 ms 908 KB
1
in14.txt AC 58 ms 3544 KB
1
in15.txt AC 87 ms 7812 KB
1
in16.txt AC 59 ms 3592 KB
1
in17.txt AC 59 ms 3640 KB
1
in18.txt AC 23 ms 1124 KB
1
in19.txt AC 20 ms 1072 KB
1
in20.txt AC 35 ms 2508 KB
1
in21.txt AC 25 ms 1196 KB
1
in22.txt AC 22 ms 1364 KB
1
in23.txt AC 25 ms 1608 KB
1
in24.txt AC 30 ms 1796 KB
1
in25.txt AC 26 ms 1944 KB
1
in26.txt AC 26 ms 2048 KB
1
in27.txt AC 27 ms 2368 KB
1
in28.txt AC 36 ms 2720 KB
1
in29.txt AC 45 ms 3380 KB
1
in30.txt AC 58 ms 3764 KB
1