회원가입
로그인
Toggle navigation
문제
문제
전체 문제
문제 출처
단계별로 풀어보기
알고리즘 분류
추가된 문제
문제 순위
문제
푼 사람이 한 명인 문제
아무도 못 푼 문제
최근 제출된 문제
최근 풀린 문제
랜덤
출처
ICPC
Olympiad
한국정보올림피아드
한국정보올림피아드시․도지역본선
전국 대학생 프로그래밍 대회 동아리 연합
대학교 대회
카카오 코드 페스티벌
Coder's High
ICPC
Regionals
World Finals
Korea Regional
Africa and the Middle East Regionals
Europe Regionals
Latin America Regionals
North America Regionals
South Pacific Regionals
문제집
대회
채점 현황
게시판
그룹
더 보기
재채점 기록
블로그
도움말
전체
공지
자유
질문
오타/오역/요청
게시판 공지
홍보
업데이트
solved.ac
글쓰기
질문 도움말
자주묻는 질문
이거 왜 틀렸을까요...
24493번 - Cereal 2
c8216
1년 전
0
30%에서 틀렸습니다가 뜹니다...
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; int N, M; int f[100100], s[100100]; vector<pii> graph[100100]; /// <정점, 원래 그래프 번호> int visited[100100]; /// 각 정점이 방문한 정점인지 확인 int eaten[100100]; /// 각 점이 먹혔는지를 확인 int node_cnt = 0; int edge_cnt = 0; queue<int> ans; queue<int> eliminated; int visited_edge[100100]; /// dfs1에서, 방문한 간선 저장 목적 int visited_node[100100]; /// 방문한 노드 번호 int ate[100100]; /// 각 간선이 이미 먹었는가? void ans_push(int x) { ans.push(x); ate[x] = 1; eaten[f[x]] = 1; eaten[s[x]] = 1; } void dfs2(int now) { //cout << now << "\n"; for(pii x: graph[now]) { int next = x.first; int edge_n = x.second; /// 간선 번호 if(ate[edge_n] != 0) continue; if(eaten[next] == 1) { //cout << " ! " << edge_n << "\n"; /// 가야하는 곳이 먹힘 eliminated.push(edge_n); ate[edge_n] = -1; } else { ans.push(edge_n); ate[edge_n] = 1; eaten[next] = 1; dfs2(next); } } } bool dfs1(int S, int lv, int before) { /// 만약 사이클이 감지되지 않고 종료되면, false 반환 /// 사이클이 감지되면, true 반환 bool X = 0; visited[S] = lv+1; visited_node[lv] = S; node_cnt += 1; //cout << S << "***\n"; for(pii x: graph[S]) { visited_edge[lv] = x.second; //cout << " - " << x.second << "\n"; if(x.second != before && visited[x.first]) { /// 간선의 끝점을 이미 방문한 경우 /// 사이클 감지 ans_push(visited_edge[lv]); if(x.first == f[x.second]) { /// 현재 간선의 끝점이 f와 같은 경우 -> f에서 시작해야 한다 /// -> 사이클의 간선 순방향으로 순회 for(int i = visited[x.first]-1; i <= lv-1; i++) { ans_push(visited_edge[i]); } } else { /// 현재 간선의 끝점이 s와 같은 경우 -> f에서 시작해야 한다 /// -> 사이클의 간선 역방향 순회 for(int i = lv-1; i >= visited[x.first]-1; i--) { ans_push(visited_edge[i]); } } /// 사이클 탐지 후에는 -> 사이클에 연결된 간선 모조리 검사 for(int i = visited[x.first]-1; i <= lv; i++) { dfs2(visited_node[i]); } return true; } if(x.second != before) { //cout << S << ": " << x.second << "\n"; edge_cnt += 1; X = dfs1(x.first, lv+1, x.second); } if(X) break; } visited_edge[lv] = -1; visited[lv] = 0; visited_node[lv] = -1; return X; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i=0;i<N;i++) { cin >> f[i] >> s[i]; graph[f[i]].push_back({s[i], i}); graph[s[i]].push_back({f[i], i}); } /// 모든 점 돌아보면서 dfs 진행 for(int i=1;i<=M;i++) { if(eaten[i] == 0) { node_cnt = 0; edge_cnt = 0; if(!dfs1(i, 0, -1)) { //cout << i << ": " << node_cnt << " " << edge_cnt+1 << " **\n\n"; assert(node_cnt == edge_cnt+1); eaten[i] = 1; dfs2(i); } } //cout << "\n\n\n"; } cout << "" << eliminated.size() << "\n"; while(!ans.empty()) { cout << ans.front()+1 << "\n"; ans.pop(); } //cout << "\n"; while(!eliminated.empty()) { cout << eliminated.front()+1 << "\n"; eliminated.pop(); } return 0; }
댓글을 작성하려면
로그인
해야 합니다.
c8216 1년 전
30%에서 틀렸습니다가 뜹니다...