[ALGORITHM] 10037 - Decorating the Pastures

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

10037번: Decorating the Pastures

대강 해석

농부 존은 N(1 <= N <= 50,000)개의 목초지를 가지고 있으며 M(1 <= M <= 100,000)개의 양방향 길이 있습니다.

길은 각기 다른 목초지를 연결하며 동일한 목초지를 연결하는 길이 있을 수도 있습니다.

각각의 목초지에 F 혹은 J로 표시를 하려 합니다. 연결된 목초지는 다른 Sign을 가지고 있어야 합니다.

J Sign의 갯수가 최대일 때 몇개 인지 알려주세요!

연결할 수 없는 경우 -1을 반환해 주세요.

 

주의할 점

모든 목초지가 길로 연결되어 있지 않을 수도 있습니다!

 

과정

1. 목초지를 돌아가며 Sign이 있는지 확인
2. 있으면 넘어가고 없는 경우 탐색 알고리즘을 통해 F혹은 J표시
3. 표시된 F와 J의 갯수중 큰 것을 반환(F와 J는 서로 바꿀수 있기 때문)
4. 만약 Sign을 표시할 수 없는 경우 -1을 반환 후 종료

예제

20 200
10 14
14 1
1 14
14 10
6 20
11 15
5 6
3 19
14 10
7 13
14 2
14 10
11 17
20 6
14 10
14 2
13 4
14 2
15 11
15 11
10 14
14 2
5 8
12 13
15 11
18 5
19 4
13 9
19 12
8 3
14 2
15 11
10 14
12 6
13 4
7 19
10 14
8 9
12 8
18 7
14 1
2 14
14 1
8 9
10 14
8 4
12 6
8 12
10 14
10 14
14 1
11 15
14 10
15 11
11 17
10 14
14 10
17 11
17 11
16 19
16 6
1 14
17 11
2 14
15 11
19 16
14 10
18 7
14 1
11 15
17 11
14 1
8 4
11 17
4 6
10 14
6 3
12 18
6 9
19 3
6 20
1 14
3 8
2 14
10 14
10 14
1 14
2 14
17 11
9 6
17 11
9 8
14 1
14 1
5 8
10 14
8 5
12 18
14 2
17 11
6 7
14 2
14 1
14 2
10 14
11 17
18 5
1 14
9 6
14 2
3 6
19 3
11 15
2 14
1 14
6 12
14 1
12 18
20 19
1 14
1 14
1 14
1 14
2 14
12 19
19 4
1 14
14 10
8 20
6 5
2 14
18 7
7 18
14 2
10 14
15 11
11 17
15 11
10 14
14 2
14 2
18 9
10 14
5 8
10 14
14 1
7 13
13 9
4 6
16 6
6 9
13 20
14 1
14 10
9 13
18 4
18 20
1 14
7 8
2 14
11 15
19 5
5 13
17 11
19 3
2 14
11 15
18 3
15 11
1 14
18 7
14 1
15 11
17 11
14 2
2 14
2 14
2 14
1 14
15 11
14 10
15 11
2 14
1 14
11 17
14 2
19 4
13 4
11 17
12 19
5 8
14 1
11 15
2 14
14 10
6 20
4 18
13 5
11 17
18 4

정답 : 13

4 4
1 2
2 3
3 4
4 1

정답 : 2

코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

typedef struct Dat{
    int node;
    char sign;
}d;

char chk[50001];
vector<int> way[50001];
int N,M;

void Initialize(){
    fill(&chk[0],&chk[50001],0);
}

void Input(){
    cin>>N>>M;

    int a,b;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        way[a].push_back(b);
        way[b].push_back(a);
    }
}

int bfs(int start){
    int jcnt=0;
    int fcnt=0;
    queue<d> q;

    q.push({start,'J'});
    chk[start]='J';

    while(!q.empty()){
        int node = q.front().node;
        char sign = q.front().sign;

        q.pop();

        if(sign=='F')
            fcnt++;
        else
            jcnt++;

        for(int i=0;i<way[node].size();i++){
            int next = way[node][i];

            if(chk[next]==sign)
                return -1;
            
            if(chk[next])
                continue;
            
            chk[next] = sign=='F'?'J':'F';
            q.push({next,chk[next]});
        }
    }
    return max(jcnt,fcnt);
}

void Solution(){
    int ret=0;
    for(int i=1;i<=N;i++){
        if(chk[i])
            continue;
        int tmp = bfs(i);
        if(tmp == -1){
            cout<<tmp<<'\n';
            return ;
        }
        ret+=tmp;
    }
    
    cout<<ret<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Initialize();
    Input();
    Solution();

    return 0;
}