#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<int> link[5002], revLink[5002];
int ex[5002], ey[5002];
int ans[5002]; /// 0: ���� �� ��, 1: ��ĥ X, 2: ��ĥ O
vector<int> ansVec;
int deg[5002];
int bccCnt;
int depth[5002], bccNum[5002], bccDeg[5002], pushed[5002];
vector<int> vertices;
int checkBCC(int x){
int ret = depth[x];
vertices.push_back(x);
for(auto y: link[x]){
if(depth[y]) ret = min(ret, depth[y]);
else depth[y] = depth[x] + 1, ret = min(ret, checkBCC(y));
}
if(ret >= depth[x]){
int B = ++bccCnt;
while(1){
int tmp = vertices.back(); vertices.pop_back();
bccNum[tmp] = B;
if(tmp == x) break;
}
}
return ret;
}
void colorBCC(int x, int c, int b){
vector<int> sumLink = link[x];
for(auto y: revLink[x]) sumLink.push_back(y);
ans[x] = c;
// printf("In ColorBCC: colored %d as %d\n", x, c);
for(auto y: sumLink){
if(bccNum[y] != b || ans[y]) continue;
colorBCC(y, 3-c, b);
}
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int x, y;
scanf("%d %d", &x, &y);
ex[i] = x, ey[i] = y;
deg[x]++;
}
while(1){
/// �ڵ� ������ �� ã��
for(int i=1; i<=n; i++) deg[i] = 0;
for(int i=1; i<=n; i++) link[i].clear(), revLink[i].clear();
for(int i=1; i<=m; i++) if(!ans[ex[i]] && !ans[ey[i]]){
link[ex[i]].push_back(ey[i]);
revLink[ey[i]].push_back(ex[i]);
deg[ex[i]]++;
}
queue<int> que;
for(int i=1; i<=n; i++) if(!ans[i] && !deg[i]) pushed[i] = 1, que.push(i);
while(!que.empty()){
int x = que.front(); que.pop();
int c = 2;
for(int y: link[x]) if(ans[y] == 2) c = 1;
for(int y: revLink[x]) if(ans[y] == 2) c = 1;
ans[x] = c;
// printf("In queue: colored %d as %d\n", x, c);
if(ans[x] == 2) for(auto y: link[x]) if(!pushed[y]) pushed[y] = 1, que.push(y);
for(auto y: revLink[x]){
deg[y]--;
if(!ans[y] && !deg[y] && !pushed[y]) pushed[y] = 1, que.push(y);
}
}
/// ��ĥ�� �� �ƴ��� Ȯ��
bool Done = 1;
for(int i=1; i<=n; i++) if(!ans[i]) Done = 0;
if(Done) break;
bccCnt = 0;
for(int i=1; i<=n; i++) bccNum[i] = depth[i] = bccDeg[i] = 0;
vertices.clear();
for(int i=1; i<=n; i++) if(!ans[i] && !bccNum[i]) depth[i] = 1, checkBCC(i);
for(int i=1; i<=m; i++) if(!ans[ex[i]] && !ans[ey[i]] && bccNum[ex[i]] != bccNum[ey[i]]) bccDeg[bccNum[ex[i]]]++;
int bccTarget = -1;
for(int i=1; i<=bccCnt; i++) if(!bccDeg[i]) bccTarget = i;
assert(bccTarget != -1);
int start = -1;
for(int i=1; i<=n; i++) if(!ans[i] && bccNum[i] == bccTarget) start = i;
assert(start != -1);
/// ��ĥ�� �ش�
colorBCC(start, 1, bccTarget);
/// �������� �̾��� ����� ��ĥ�� �ش�
for(int i=1; i<=n; i++) if(bccNum[i] == bccTarget){
if(ans[i] == 2) for(int j: revLink[i]) if(!ans[j]) ans[j] = 1;
}
}
for(int i=1; i<=n; i++) if(ans[i] == 2) ansVec.push_back(i);
printf("%d\n", (int)ansVec.size());
for(auto x: ansVec) printf("%d ", x);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
1000 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| 3 |
Correct |
2 ms |
724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
852 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1620 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
