Submission #42594

ソースコード

?
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
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 10005;
typedef pair<int ,int>P;
//ノードの番号
int num[SIZE]={};
//order->正順　rev->逆順
vector<int> order[SIZE],rev[SIZE];
//フラグ用配列
int flag[SIZE]={};
set<P> flag2;
int cnt[SIZE][2]={};
int dfs(int i,int index);
void dfs2(int i);
//union find用配列
int parents[SIZE];
//union find用関数　3つ
int find(int x);
bool same(int x,int y);
void updata(int x, int y);
priority_queue<P, vector<P> > que;
int main(){
int n,m;
scanf("%d %d",&n,&m);
//unionfind配列　初期化
for(int i=0;i<SIZE;i++){
parents[i]=i;
}
for(int i=0;i<m;i++){
int a,b;
scanf("%d %d",&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 = dfs(i,index)+1;
}
}
int ans = 0;
while(!que.empty()){
P a=que.top();
que.pop();
if(flag[a.second] != 0){
continue;
}
ans++;
dfs2(a.second);
}
//グループが一つしかなかったら
if(ans == 1){
//新しく道路を造らなくて良い
printf("0\n");
}else{
int sum1=0,sum2=0;
for(int i=0;i<SIZE;i++){
flag[i]=0;
}
for(int i=0;i<n;i++){
int temp=find(i);
if(flag[temp] == 1)continue;
if(cnt[temp][0] == 0)sum1++;
if(cnt[temp][1] == 0)sum2++;
flag[temp]=1;
}
printf("%d\n",max(sum1,sum2));
}
/*
for(int i=0;i<n;i++){
printf("%d %d\n",i,num[i]);
}
*/
return 0;
}
int find(int x){
//x=親を知りたい数字
if(x == parents[x]){
return x;
}else{
return parents[x]=find(parents[x]);
}
}
//二つの数字x,yの親を調べて同じかどうか調べる
bool same(int x,int y){
x = find(x);
y = find(y);
return x==y;
}
void updata(int x, int y){
x = find(x);
y = find(y);
if(x==y){
return;
}
parents[y]=x;
return;
}
int dfs(int i,int index){
//今居るところに-1
num[i] = -1;
for(int j=0;j<order[i].size();j++){
int next = order[i][j];
//次行けるところが行っていないところだったら
if(num[next] == 0){
index = dfs(next,index)+1;
}
}
//ノードとコストを大きい順にソート
que.push(P(index, i));
num[i]=index;
return index;
}
//行ける向きを逆順にする
void dfs2(int i){
flag[i] = -1;
for(int j=0; j<rev[i].size();j++){
int next = rev[i][j];
P a = P(min(i,next),max(i,next));
if(flag[next] == 0){
updata(i,next);
dfs2(next);
}else if(!same(i,next) && flag2.find(a) == flag2.end()){
cnt[find(i)][1]++;
cnt[find(next)][0]++;
flag2.insert(a);
}
}
return;
}

ステータス

項目 データ
問題 0964 - 道路網改修
ユーザー名 ei1616
投稿日時 2018-09-03 18:12:10
言語 C++11
状態 Accepted
得点 14
ソースコード長 2891 Byte
最大実行時間 78 ms
最大メモリ使用量 7428 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 35 ms 992 KB
1
in2.txt AC 29 ms 976 KB
1
in3.txt AC 21 ms 1012 KB
1
in4.txt AC 23 ms 1140 KB
1
in5.txt AC 26 ms 1080 KB
1
in6.txt AC 28 ms 1312 KB
1
in7.txt AC 27 ms 3052 KB
1
in8.txt AC 23 ms 1592 KB
1
in9.txt AC 44 ms 3028 KB
1
in10.txt AC 39 ms 2344 KB
1
in11.txt AC 32 ms 1840 KB
1
in12.txt AC 28 ms 2652 KB
1
in13.txt AC 18 ms 1068 KB
1
in14.txt AC 43 ms 3480 KB
1
in15.txt AC 78 ms 7428 KB
1
in16.txt AC 43 ms 3580 KB
1
in17.txt AC 39 ms 3556 KB
1
in18.txt AC 17 ms 984 KB
1
in19.txt AC 24 ms 1044 KB
1
in20.txt AC 31 ms 2104 KB
1
in21.txt AC 21 ms 1220 KB
1
in22.txt AC 21 ms 1292 KB
1
in23.txt AC 31 ms 1496 KB
1
in24.txt AC 22 ms 1684 KB
1
in25.txt AC 28 ms 1748 KB
1
in26.txt AC 25 ms 1804 KB
1
in27.txt AC 31 ms 2112 KB
1
in28.txt AC 29 ms 2492 KB
1
in29.txt AC 47 ms 3260 KB
1
in30.txt AC 42 ms 3504 KB
1