[BOJ 24493] Cereal 2

https://www.acmicpc.net/problem/24493

24493번: Cereal 2

 

- 문제 요약

 

농부 John의 젖소들은 시리얼을 너무 좋아해서 한 끼에 시리얼 한 상자를 다 먹습니다.

현재 M(2<=M<=10^5)개 종류의 시리얼이 각 한 상자씩 있습니다.

N(1<=N<=10^5)마리의 젖소들은 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 존재합니다.

젖소들은 아래의 과정에 따라 시리얼을 선택합니다.

1. 가장 좋아하는 시리얼이 아직 있다면 그 시리얼 한 상자를 선택합니다.
2. 그렇지 않으면 두 번째로 좋아하는 시리얼이 남아있나 확인하고, 남아있다면 그 시리얼 상자를 하나 가져갑니다.
3. 그렇지 않다면 소는 울면서 시리얼을 먹지 않고 자리를 떠날 것입니다.

가능한 모든 소가 자신이 좋아하는 시리얼을 먹을 수 있도록 한다면, 시리얼을 하나도 먹지 못하는 소의 마릿수는 최소 몇 마리인지를 N개의 줄에 출력하세요.

 

 

- 알고리즘 정리

 

M개의 시리얼을 정점으로, 각 소가 가장 좋아하는 시리얼에서 두 번째로 좋아하는 시리얼을 향하도록 하는 그래프를 그려놓고, 이 상태에서 dfs를 돌리면 문제를 해결할 수 있습니다.
이 경우, 사이클 발생 여부를 확인하면서 dfs를 시행해줘야 합니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;
 
struct st{
    int cow;
    int to;
    bool F;
    st(){};
    st(int cow,int to,bool F):cow(cow),to(to),F(F){};
};
int n,m,ignore_edge=-1,first_cereal=-1,hungry;
vector<st>adj[100001];
bool visited_cycle[100001],visited[100001],gets_cereal[100001];
queue<int>order;

void find_cycle(int cur,int prev=-1){
    visited_cycle[cur]=true;
    for(st next:adj[cur]){
        if(visited_cycle[next.to]){
            if(first_cereal==-1&&next.to!=prev){
                if(next.F){
                    first_cereal=next.to; 
                }
				else{
                    first_cereal=cur;
                }
                ignore_edge=next.cow; 
                order.push(next.cow);
                gets_cereal[next.cow]=true;
            }
        }
		else{
            find_cycle(next.to,cur);
        }
    }
}
 
void dfs(int cur){
    visited[cur]=true;
    for(st next:adj[cur]){
        if(!visited[next.to]&&next.cow!=ignore_edge){ 
            gets_cereal[next.cow] = true;
            order.push(next.cow);
            dfs(next.to);
        }
    }
}
 
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(st(i+1,b,false));
        adj[b].push_back(st(i+1,a,true));
    }
    for(int i=1;i<=m;i++){
        first_cereal=-1;
        ignore_edge=-1;
        if(!visited[i]){
            find_cycle(i);           
            if(first_cereal>0){
                dfs(first_cereal);
            }
			else{
                dfs(i);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!gets_cereal[i]){
            ++hungry;
            order.push(i);
        } 
    }
    cout<<hungry<<endl;
    while(!order.empty()){
        cout<<order.front()<<'\n'; 
        order.pop();
    }
}

코드 제출 결과