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

ajttnd 4년 전 0

출력초과문제인데 출력사항에서 문제는 없는것 같습니다만은...코드에 주석을 달긴했는데

제 생각위주로 처음 단절점 구현해본거라 구조적으로 문제인지도 궁금합니다..

#include <iostream>
#include <list>
#include <string.h>
using namespace std;
//order 도착순서. low 갈수있는 노드중 가장순서빠른것.
struct st {
	int order, low;
	st() {}
	st(int order, int low) :order(order), low(low) {}
};
st ary[10100];
list<int> li[10100];
int v, e, idx;
int rescheck[10100];
int visit[10100], p[10100], res[10100];
int treecnt, tree[10100];//tree[i] : i를 루트로하는 tree의 node개수가 담김.(나중에 루트노드일때 단절점인지확인위함.)
void dfs(int node) {
	treecnt++;
	list<int>::iterator it;
	//연결된 정점탐색하며 쭉내려감
	for (it = li[node].begin(); it != li[node].end(); it++) {
		int next = *it;
		if (visit[next] == 0) {
			p[next] = node;
			visit[next] = 1;
			ary[next].order = idx;
			ary[next].low = ary[next].order;
			idx++;
			dfs(next);
		}
	}
	//단말노드에 도달시 그정점의 부모를 제외한 다른 정점과의 간선을 탐색.
	int MIN = ary[node].low;
	for (it = li[node].begin(); it != li[node].end(); it++) {
		int next = *it;
		if (MIN > ary[next].low) {
			MIN = ary[next].low;
		}
	}
	ary[node].low = MIN;

}
//루트노드가 단절점인지 여부에 루트노드가 들어올시 자식노드 탐색을통해 단지 tree의 node개수파악.
void checkdfs(int node) {
	treecnt++;
	list<int>::iterator it;
	for (it = li[node].begin(); it != li[node].end(); it++) {
		int next = *it;
		if (visit[next] == 0) {
			visit[next] = 1;
			checkdfs(next);
		}
	}
}
int main() {
	scanf("%d%d", &v, &e);
	for (int i = 0; i < e; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		//양방향.
		li[a].push_back(b);
		li[b].push_back(a);
	}
	//dfs search. 모든정점에 대하여.
	for (int i = 1; i <= v; i++) {
		idx = 1;
		if (visit[i] == 0) {
			p[i] = i; // root의 부모는 root.
			visit[i] = 1;
			ary[i].order = idx;
			ary[i].low = ary[i].order; //low==order 초기화값. 
			idx++;
			dfs(i);
			tree[i] = treecnt;
			treecnt = 0;
		}
	}
	int cnt = 0;
	for (int i = 1; i <= v; i++) {
		//root node 일떄
		if (p[i] == i) {
			int size = li[i].size();
			if (size >= 2 && rescheck[i] == 0) {
				memset(visit, 0, sizeof(visit));
				visit[i] = 1;
				visit[li[i].back()] = 1;
				checkdfs(li[i].back());
				if (treecnt != tree[i] - 1) {//root를 제외한 트리의 노드개수가 tree[i]-1이면 단절이 없다.
					rescheck[i] = 1;
					res[cnt] = i;
					cnt++;
				}
				treecnt = 0;
			}
		}
		//일반적.
		//선택정점의 순서와 연결정점의 low 비교.
		else {
			list<int>::iterator it;
			for (it = li[i].begin(); it != li[i].end(); it++) {
				int x = *it;
				if ((ary[x].low >= ary[i].order) && rescheck[i] == 0) {
					rescheck[i] = 1;
					res[cnt] = i;
					cnt++;
				}
			}
		}
	}
	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d ", res[i]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

출력초과 문제 질문드립니다.

ajttnd 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말