글 읽기 - 출력초과 질문드립니다

p_ce1052 3년 전 0

scc를 위상정렬했을 때 indegree가 0인 정점이 2개 이상이라면 Confused

아니라면 indegree가 0인 유일한 scc에 속하는 모든 정점들을 오름차순으로 출력해주었습니다.

출력초과는 어디서 발생하는건가요? 도저히 모르겠습니다

#include<bits/stdc++.h>
using namespace std;
vector<int>graph[100005];
int discovered[100005];
int scc_id[100005];
int indegree[100005];
int counter = 1;
int scc = 1;
stack<int>st;
void init(int n){
	scc = 1,counter = 1;
	for(int i=1; i<=n; i++){
		graph[i].clear();
		discovered[i] = 0;
		scc_id[i] = 0;
		indegree[i] = 0;
	}
}
int dfs(int cur){
	discovered[cur] = counter++;
	int ret = discovered[cur];
	st.push(cur);
	for(int i=0; i<graph[cur].size(); i++){
		int nxt = graph[cur][i];
		if(!discovered[nxt]) ret = min(ret,dfs(nxt));
		else if(!scc_id[nxt]) ret = min(ret,discovered[nxt]);
	}
	if(ret==discovered[cur]){
		while(st.size() && st.top()!=cur){
			scc_id[st.top()] = scc;
			st.pop();
		}
		scc_id[st.top()] = scc;
		st.pop();
		scc++;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		init(n);
		while(m--){
			int a,b;
			cin>>a>>b;
			a++;
			b++;
			graph[a].push_back(b);
		}
		for(int i=1; i<=n; i++) if(!discovered[i]) dfs(i);
		int ans = 0;
		for(int i=1; i<=n; i++){
			for(int j=0; j<graph[i].size(); j++){
				int nxt = graph[i][j];
				if(scc_id[i]!=scc_id[nxt]) indegree[scc_id[nxt]]++; 
			}
		}
	
		for(int i=1; i<scc; i++) if(!indegree[i]) ans++;
		if(ans>=2) cout<<"Confused"<<'\n';
		else{
			vector<int>ret;
			for(int i=1; i<scc; i++){
				if(!indegree[i]){
					for(int j=1; j<=n; j++){
						if(scc_id[j]==i) ret.push_back(j);
					}
					break;
				}
			}
			sort(ret.begin(),ret.end());
			for(auto a:ret) cout<<a-1<<'\n';
			cout<<'\n';
		}
	}
}

p_ce1052 3년 전 0

해결되었습니다 confused 뒤에도 개형문자를 2개 붙여야 합니다....

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

문제

문제

출처

ICPC

출력초과 질문드립니다

p_ce1052 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말