글 읽기 - 고수분들께 질문 6543번

(追記) (追記ここまで)

고수분들께 질문 6543번

6543번 - 그래프의 싱크

chanmin4 6년 전 0

ssc를 만들고 outdgree가 0인 ssc안의 원소를 resultcount배열에 넣고 정렬해서 출력하는형식으로 짯습니다 그런데 자꾸 틀렸습니다가 채점되네요 어느부분에서 문제가 생기는기 알려주시면 감사드리겠습니다!!

#include<iostream> 
#include<vector>
#include<string>
#include<algorithm>
#include<cmath> 
#include<stack>
#include<queue>
using namespace std;
typedef pair<int, int>P;
typedef long long ll;
int n, m, cnt = 0, SN = 0;
vector<int>dfsn;
stack<int>s;
vector<bool>finished;
vector<vector<int>>adj;
vector<vector<int>>SCC;
vector<int>sn;
vector<int>resultcount;
int DFS(int cur) {
 dfsn[cur] = ++cnt;
 s.push(cur);
 int result = dfsn[cur];
 for (int next : adj[cur]) {
 if (dfsn[next]==0)result = min(result, DFS(next));
 else if (!finished[next])result = min(result, dfsn[next]);
 }
 if (result == cur) {
 vector<int>curscc;
 while (1) {
 int t = s.top();
 s.pop();
 curscc.push_back(t);
 finished[t] = true;
 sn[t] = SN;
 if (t == cur)break;
 }
 SCC.push_back(curscc);
 SN++;
 }
 return result;
}
int main() {
 cin.tie(0);
 cout.tie(0);
 ios::sync_with_stdio(false);
 while (1) {
 cin >> n;
 sn.resize(n + 1);
 adj.resize(n + 1);
 finished.resize(n + 1);
 dfsn.resize(n + 1);
 if (n == 0)return 0;
 cin >> m;
 for (int i = 0; i < m; i++) {
 int a, b;
 cin >> a >> b;
 adj[a].push_back(b);
 }
 for (int i = 1; i <= n; i++) {
 if (dfsn[i] == 0)DFS(i);
 }
 for (auto &k : SCC) {//sn안의 원소들
 bool check = true;
 for (int j : k) {
 for (int a : adj[j]) {
 if (sn[a] != sn[j]) {
 check = false;
 break;
 }
 }
 if (!check)break;
 }
 if (check) {
 for (int i = 0; i < k.size(); i++) {
 resultcount.push_back(k.at(i));
 }
 }
 }
 sort(resultcount.begin(), resultcount.end());
 for (int i = 0; i < resultcount.size(); i++) {
 cout << resultcount[i] << " ";
 }
 cout << "\n";
 sn.clear();
 finished.clear();
 adj.clear();
 dfsn.clear();
 SCC.clear();
 resultcount.clear();
 cnt = 0;
 SN = 0;
 }
 }

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

고수분들께 질문 6543번

chanmin4 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말